is quitting smoking np hard?

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > is quitting smoking np hard?

«‹›6 »

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

hbag posted:

if i need to understand this to get a computer touching job i might as well just put in my application at mcdonalds now

Dijkstracula posted:

just count the depth of your nested loops, bingo bango

# ? Aug 17, 2023 20:46

Adbot: ADBOT LOVES YOU

# ? Apr 27, 2024 14:41

post hole digger: Mar 21, 2011

my brother is a glazier with a high school education and does more advanced math than i do as a computer toucher every day dont worry about it.

# ? Aug 17, 2023 20:49

hbag: Feb 13, 2021

Dijkstracula posted:

just count the depth of your nested loops, bingo bango

so id end up with, for example, O(3) instead of "O(n log n) or whatever"
that doesnt seem right

# ? Aug 17, 2023 20:49

hbag: Feb 13, 2021

post hole digger posted:

my brother is a glazier with a high school education and does more advanced math than i do as a computer toucher every day dont worry about it.

thats why i said mcdonalds and not window poo poo

# ? Aug 17, 2023 20:50

post hole digger: Mar 21, 2011

the point is you dont need to know math to do a lot of things, not that you should install glass instead.

# ? Aug 17, 2023 20:50

hbag: Feb 13, 2021

yeah but "glaziers do harder math" doesnt really make the computer touching math any easier

# ? Aug 17, 2023 20:54

post hole digger: Mar 21, 2011

i dont do any math at all so maybe get a job in security or cloud administration. i should have just said that.

post hole digger fucked around with this message at 20:58 on Aug 17, 2023

# ? Aug 17, 2023 20:56

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

hbag posted:

so id end up with, for example, O(3) instead of "O(n log n) or whatever"
that doesnt seem right

oh boy you really didn�t learn this huh

no, if you had three nested loops, say:

code:

for i = 0..n:
  for j = 0..n:
    for k = 0..n:
      // something involving i, j, k

how many times do you execute the line with the comment on it! n times for each value of j, to which there are n, and that happens n times for each value of i, so it�d be n*n*n and if the body of the inner loop has constant time complexity, then you�d have O(n^3) * O(1) = O(n^3)

with some similar reasoning you can show the same thing with other bounds on the loop variables (like e.g. j from 0..i and k from 0..j)

by contrast you often see log terms when you split work into two at each iteration, like in binary search ( O(log n) since you are subdividing the space by half each time) or many search algorithms (O(n log n) because you also divide the search space by 2 but do O(n) work each time you do it)

# ? Aug 17, 2023 20:57

hbag: Feb 13, 2021

...uh-huh

# ? Aug 17, 2023 20:59

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

Cybernetic Vermin posted:

people go something like:

f(x,y) \in O(g(x,y)) iff there exists c and m such that f(x,y) < m*g(x) for all x>c and y>c

issue is that this program is then in O(x+y):
code:
int f(int x, int y) {
    if(x==0) {
        return fexp(y,y);
    }
    else {
        return x+y;
    }
}
since picking c>0 immediately makes the exponentiation disappear.

yeah i mean weird-rear end non-monotonic cost functions certainly do give this loosy-goosy intuitive analytical tool some trouble, you got that right

# ? Aug 17, 2023 21:01

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

hbag posted:

...uh-huh

try it yourself: consider a single nested loop:

code:

for i = 0..n:
  for j = 0..i:
    // �

what are the values of i and j that could be in the loop? (0,0),(1,0),(1,1),(2,0)..(n-1, (n-1)-1). how many pairs of numbers are there, �roughly�? well, roughly the first element runs from 0 to n, as does the second one, so the number of total pairs feels like it�s quadratic in n, so a guess would be that this has time complexity O(n^2). and it does! (convince yourself that by a similar reasoning, 0+1+2+..n which is (n * (n+1))/2, if you expand it out and throw away the constant factor, also gives you n^2)

its not impossible or obtuse if you keep it high-level like this, it just takes practice to see the common patterns

# ? Aug 17, 2023 21:07

Cybernetic Vermin: Apr 18, 2005

rjmccall posted:

yeah i mean weird-rear end non-monotonic cost functions certainly do give this loosy-goosy intuitive analytical tool some trouble, you got that right

it is not a loosy-goosy intuitive tool though, it is just abused a lot.

# ? Aug 17, 2023 21:08

hbag: Feb 13, 2021

Dijkstracula posted:

try it yourself: consider a single nested loop:
code:
for i = 0..n:
  for j = 0..i:
    // �
what are the values of i and j that could be in the loop? (0,0),(1,0),(1,1),(2,0)..(n-1, (n-1)-1). how many pairs of numbers are there, �roughly�? well, roughly the first element runs from 0 to n, as does the second one, so the number of total pairs feels like it�s quadratic in n, so a guess would be that this has time complexity O(n^2). and it does! (convince yourself that by a similar reasoning, 0+1+2+..n which is (n * (n+1))/2, if you expand it out and throw away the constant factor, also gives you n^2)

its not impossible or obtuse if you keep it high-level like this, it just takes practice to see the common patterns

i will forever curse my high school math teacher for just neglecting half the class because even this is just very difficult to get

# ? Aug 17, 2023 21:09

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

well if you�re only in high school I don�t know when you would have learned any of this, I thought from your past posts you were graduating uni or something

also I�ll say it again, you don�t get stuff by reading my bad posts that I�m typing on my phone whilst I�m pooping, you get stuff by actually playing around with the concepts yourself

# ? Aug 17, 2023 21:11

hbag: Feb 13, 2021

i am 21 years old and two years into a compsci degree

# ? Aug 17, 2023 21:17

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

well then you�ll have plenty of time to get a sense of rough and ready complexity analysis before someone makes you do it in a whiteboard interview

# ? Aug 17, 2023 21:20

echinopsis: Apr 13, 2004; by Fluffdaddy

I offer nicotine replacement products (NRT) to people

I like to offer hopefully some encouraging advice :

every cigarette you don�t smoke is good
a 20 a day smoker going to 15 a day is an improvement

failure to totally quit can lead people to a �gently caress it� place, so focusing on progress is a good thing to
do

if you quit and start again, well, that�s better than not quitting because you smoked less cigarettes overall

if you simply can�t escape nicotine dependency and end up on NRT for life that�s ok. less than ideal sure but smoking is just so fuckin bad for that almost anything else is a better alternative. especially vaping, basically a drop in replacement, which has its own issues of course but is still better than smoking

# ? Aug 17, 2023 21:24

hbag: Feb 13, 2021

in terms of nicotine cigarettes suck compared to vapes
in terms of looking cool though...

# ? Aug 17, 2023 21:26

echinopsis: Apr 13, 2004; by Fluffdaddy

yeah this is a thread about objectively the coolest thing you can do and it loving changed up i to god drat nerd-o-rama

# ? Aug 17, 2023 21:29

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

Cybernetic Vermin posted:

it is not a loosy-goosy intuitive tool though, it is just abused a lot.

look, if you�re studying it formally for some mysterious reason then sure, you might as well find a definition that doesn�t have that specific flaw. but who cares, it is not actually mathematically interesting, it is a communicative tool for establishing broad categories of asymptotic cost. usually people don�t even bother to define what costs they�re measuring, just some nebulous idea of �steps�, and it�s just as communicatively useful.

if precise counts for some cost are actually important then you should probably give an actual function for it instead of just a theta class

there are all sorts of bizarre non-monotonic cost functions that are not summarized well by a theta class, like a function that takes trillions of steps for n <= 5 but then f(n) = 2n otherwise. but usually the assumption is that the inputs to this cost function are various measurements of the size of the input, and why would smaller inputs ever uniformly be more expensive than larger ones

# ? Aug 17, 2023 21:37

distortion park: Apr 25, 2011

echinopsis posted:

I offer nicotine replacement products (NRT) to people

I like to offer hopefully some encouraging advice :

every cigarette you don’t smoke is good
a 20 a day smoker going to 15 a day is an improvement

failure to totally quit can lead people to a “gently caress it” place, so focusing on progress is a good thing to
do

if you quit and start again, well, that’s better than not quitting because you smoked less cigarettes overall

if you simply can’t escape nicotine dependency and end up on NRT for life that’s ok. less than ideal sure but smoking is just so fuckin bad for that almost anything else is a better alternative. especially vaping, basically a drop in replacement, which has its own issues of course but is still better than smoking

this is the approach I took to giving up meat after reading an interview with Ezra Klein (probably very uncool but w/e) about how he became vegan. It worked great, was much easier more robust to just eat less meat than making being vegetarian part of my identity. Perhaps easier that quitting smoking

# ? Aug 17, 2023 21:38

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

echinopsis posted:

yeah this is a thread about objectively the coolest thing you can do and it loving changed up i to god drat nerd-o-rama

look i can�t let this person get away with being right in a way i disagree with

# ? Aug 17, 2023 21:38

distortion park: Apr 25, 2011

don't watch In The Mood for Love if you wanna give up smoking, it looks Extremely Cool in that

# ? Aug 17, 2023 21:40

akadajet: Sep 14, 2003

I don�t like how cigarette smoke smells and I�m glad it�s not as common anymore

# ? Aug 17, 2023 21:45

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

I do love the smell of pipe smoke tho

# ? Aug 17, 2023 21:48

Cybernetic Vermin: Apr 18, 2005

rjmccall posted:

look, if you�re studying it formally for some mysterious reason then sure, you might as well find a definition that doesn�t have that specific flaw. but who cares, it is not actually mathematically interesting, it is a communicative tool for establishing broad categories of asymptotic cost. usually people don�t even bother to define what costs they�re measuring, just some nebulous idea of �steps�, and it�s just as communicatively useful.

i and just about every single person in existence doing algorithmics work use big-o, intend a precise meaning, and if we're abandoning the meaning would need to invent new terminology for what was previously intended.

rjmccall posted:

if precise counts for some cost are actually important then you should probably give an actual function for it instead of just a theta class

this is nonsense, the reason it is used is that it is often extremely difficult to establish a precise function, and for algorithmics in particular it would be tied to then contrived assumptions (e.g. precise bit layouts of inputs, exact computational model details). if you do like finite automata state complexity work you do try to escape to precise bounds, but even in that simple case there is a lot of work expended accounting for the smallest details (e.g. restate the proof for the case where you are permitted more than one initial state).

and that is for big-o's, thetas is extremely optimistic, there's so little in the world we have lower bounds for.

rjmccall posted:

there are all sorts of bizarre non-monotonic cost functions that are not summarized well by a theta class, like a function that takes trillions of steps for n <= 5 but then f(n) = 2n otherwise. but usually the assumption is that the inputs to this cost function are various measurements of the size of the input, and why would smaller inputs ever uniformly be more expensive than larger ones

for a single variable it is fine is the thing, there's no real need for monotonicity. the easy way by setting the cutoff c=6 to get rid of n<=5, but also you can just set the linear factor m=max {f(1), ..., f(5)} and c=1 whenenever only a finite number of elements exceed the intended function.

the entire point of the original point is that it is a small technical niggle that a lot of people and places missed, that as you go to multivariate functions you need to actually make a monotonicity assumption of some kind (i.e. insert a suitable 'max'), and it is not necessarily that obvious how to do it even, at least if you want to cover the reals (which, granted, for algorithmics you usually would not care about).

# ? Aug 17, 2023 22:06

akadajet: Sep 14, 2003

I like that there are two earnest and completely unrelated discussions going on here.

# ? Aug 17, 2023 22:07

AlbertFlasher: Feb 14, 2006; Hulk Hogan and the Wrestling Boot Band

akadajet posted:

I don�t like how cigarette smoke smells and I�m glad it�s not as common anymore

# ? Aug 17, 2023 22:13

rotor: Jun 11, 2001; classic case of pineapple derangement syndrome

echinopsis posted:

I offer nicotine replacement products (NRT) to people

please everyone, this is the Big O notation thread, try to stay on topic

# ? Aug 17, 2023 22:13

hbag: Feb 13, 2021

earlier i was genuinely confused because i couldnt find the big o notation thread in my bookmarks lmao

# ? Aug 17, 2023 22:14

Armitag3: Mar 15, 2020; Forget it Jake, it's cybertown.

rotor posted:

please everyone, this is the Big O notation thread, try to stay on topic

i only smoke Big O. Big O, assert your wild side

# ? Aug 17, 2023 22:14

well-read undead: Dec 13, 2022

in my experience of doing actual programming for money, big O notation is something talked about in interviews and literally nowhere else. i've never heard a programmer mention big O while actually doing a job

for the minority of roles where writing high performance algorithms is a core requirement, maybe it's a thing, but we simply leave those roles to the math nerds who, for some unknown reason, love that poo poo

~on the other topic~

it is folly for an ex-smoker to opine to other would-be ex-smokers about the "right way" to quit, because different people are different

my partner quit smoking 2 years ago after smoking for 25 years. she hasn't had a cigarette since, and she will never touch one again, but she misses them ALL THE TIME, even now, even though she understands exactly how they played on her reward mechanisms

# ? Aug 17, 2023 22:21

Cybernetic Vermin: Apr 18, 2005

yeah, i am absolutely not trying to argue that i am expressing something of universal interest here

mostly wanted to comment as saying "x is easy" is misleading (and possibly unnecessarily disheartening for those that then try to read the wikipedia or so) when really its "you can blag your way through x easily enough"

# ? Aug 17, 2023 22:25

rotor: Jun 11, 2001; classic case of pineapple derangement syndrome

oh its folly to opine is it?

# ? Aug 17, 2023 22:25

rotor: Jun 11, 2001; classic case of pineapple derangement syndrome

fellows, be good chaps and refrain from opining, if you would

# ? Aug 17, 2023 22:28

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

well-read undead posted:

for the minority of roles where writing high performance algorithms is a core requirement, maybe it's a thing

if anything this is the situation where it isn�t a thing; if you�re doing something where you�re twiddling bits to eke out a 5% improvement in a tensor computation or whatever, that constant factor would just disappear in the complexity analysis

# ? Aug 17, 2023 22:30

well-read undead: Dec 13, 2022

rotor posted:

oh its folly to opine is it?

i'll give you an opining pass

# ? Aug 17, 2023 22:32

OldAlias: Nov 2, 2013

well-read undead posted:

in my experience of doing actual programming for money, big O notation is something talked about in interviews and literally nowhere else. i've never heard a programmer mention big O while actually doing a job

for the minority of roles where writing high performance algorithms is a core requirement, maybe it's a thing, but we simply leave those roles to the math nerds who, for some unknown reason, love that poo poo

~on the other topic~

it is folly for an ex-smoker to opine to other would-be ex-smokers about the "right way" to quit, because different people are different

my partner quit smoking 2 years ago after smoking for 25 years. she hasn't had a cigarette since, and she will never touch one again, but she misses them ALL THE TIME, even now, even though she understands exactly how they played on her reward mechanisms

agreed tho having a general sense of time and space complexity and how performant or not your poo poo is is a thing any programmer should be aware of at least on some level

also agreed

# ? Aug 17, 2023 23:17

echinopsis: Apr 13, 2004; by Fluffdaddy

show me your O face

# ? Aug 17, 2023 23:20

Adbot: ADBOT LOVES YOU

# ? Apr 27, 2024 14:41

hbag: Feb 13, 2021

OldAlias posted:

agreed tho having a general sense of time and space complexity and how performant or not your poo poo is is a thing any programmer should be aware of at least on some level

also agreed

i think i have a grasp on what makes a function take longer but i could not write it out as math

# ? Aug 17, 2023 23:22

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > is quitting smoking np hard?

«‹›6 »