In Complexity Analysis why is ++ considered to be

问题:

In my Computer Science II class, the professor considers ++,--,*=, etc. to be 2 operations. However, at the Assembly level this is not really two operations. Can someone explain or is this just for the sake of simplicity?

回答1:

I'd actually consider it to be 3 operations: read, increment (or whatever), write. That's assuming it's reading from some sort of shared memory into some sort of local storage (e.g. register or stack), operating on the local storage, then writing back.

How many operations it is at assembly level will depend on what you're incrementing, the platform, the hardware etc.

回答2:

Because ++ (ex: b++) is a simplification of

b = b + 1 

There are two operations there, the addition (b + 1) and then the assignment of the value of the addition to the original variable.

回答3:

Why bother when doing complexity analysis? It is just O(1) :-)

EDIT: Please let me know why when you vote it down. Since the question is tagged complexity, I assume big O notion is the most important, rather than the actual constants. Besides, as already mentioned in other answers, how many operations this is depends on a lot of factors: the way you count operations, platform, compiler, etc.

回答4:

I am gonna throw a few guesses.

• Is your professor is referring to interpreted languages?
• ++i is different than i++ maybe he's referring to that?

• Maybe his assembly lang of choice needs the intermediate storage variable?

  add reg_temp, reg_i, 1
  mov reg_i, reg_temp
  

回答5:

Isn't it an addition plus a setter?

Similar to i+=1?

回答6:

The prof is probably just referring to having to take the value, add 1 to it and then assign it back to the variable.

回答7:

At the assembly level everything is done in registers so having a variable in A

ADD AX,1

However, in compiled languages everything has to be stored so i++ becomes (in pseudo assembly)

MOV AX,i
ADD AX, 1
MOV i, AX

Which is three operations...Unless I have forgotten my basic architecture completely...

回答8:

You reminded me of a Kinda "Jury is not out" problem that I heard a long time ago.

"Preincrement is faster than postincrement"

I just did a quick google search.

1. Lots of people still hold that as true.
2. Others contend that Compilers are so optimized, the comparative high level code code can't be benchmarked.
3. Yet other people contend that there is no difference.

回答9:

It should be more than 2 in my opinion since it has two meanings depending on context and I always have to remind myself of them when I see it.

a = b++ is the same as a = b; b = b + 1

and

a = ++b is the same as b = b + 1; a = b

This is enough of a confusion to send most first year students off the cliff.