How to calculate worst case analysis of this algorithm?_问答_开发者

sum = 0;
for(int i = 0; i < N; i++)
    for(int j = i; j >= 0; j--)
       sum++;

From what I understand, the first line is 1 operation, 2nd line is (i+1) operations, 3rd line is (i-1) operations, and 4th line is n oper开发者_运维百科ations. Does this mean that the running time would be 1 + (i+1)(i-1) + n? It's just these last steps that confuse me.

To analyze the algorithm you don't want to go line by line asking "how much time does this particular line contribute?" The reason is that each line doesn't execute the same number of times. For example, the innermost line is executed a whole bunch of times, compared to the first line which is run just once.

To analyze an algorithm like this, try identifying some quantity whose value is within a constant factor of the total runtime of the algorithm. In this case, that quantity would probably be "how many times does the line sum++ execute?", since if we know this value, we know the total amount of time that's spent by the two loops in the algorithm. To figure this out, let's trace out what happens with these loops. On the first iteration of the outer loop, i == 0 and so the inner loop will execute exactly once (counting down from 0 to 0). On the second iteration of the outer loop, i == 1 and the inner loop executes exactly twice (first with j == 1, once with j == 0. More generally, on the kth iteration of the outer loop, the inner loop executes k + 1 times. This means that the total number of iterations of the innermost loop is given by

1 + 2 + 3 + ... + N

This quantity can be shown to be equal to

N (N + 1)      N^2 + N    N^2    N
---------   =  ------- =  --- + ---
    2             2        2     2

Of these two terms, the N^2 / 2 term is the dominant growth term, and so if we ignore its constant factors we get a runtime of O(N²).

Don't look at this answer as something you should memorize - think of all of the steps required to get to the answer. We started by finding some quantity to count, and then saw how that quantity was influenced by the execution of the loops. From this, we were able to derive a mathematical expression for that quantity, which we then simplified. Finally, we took the resulting expression and determined the dominant term, which serves as the big-O for the overall function.

Work from inside-out.

sum++

This is a single operation on it's own, as it doesn't repeat.

for(int j = i; j >= 0; j--)

This loops i+1 times. There are several operations in there, but you probably don't mean to count the number of asm instructions. So I'll assume for this question this is a multiplier of i+1. Since the loop contents is a single operation, the loop and its block perform i+1 operations.

for(int i = 0; i < N; i++)

This loops N times. So as before, this is a multiplier of N. Since the block performs i+1 operations, this loop performs N(N+1)/2 operations in total. And that's your answer! If you want to consider big-O complexity, then this simplifies to O(N²).

It's not additive: the inner loop happens once for EACH iteration of the outer loop. So it's O(n²).

By the way, this is a good example of why we use asymptotic notation for this kind of thing -- depending on the definition of "operation" the exact details of the count could vary pretty widely. (Like, is sum++ a single operation, or is it add sum to 1 giving temp; load temp to sum?) But since we know that all that can be hidden in a constant factor, it's still going to be O(n²).

No; you don't count a specific number of operations for each line and then add them up. The entire point of constructions like 'for' is to make it possible for a given line of code to run more than once. You're supposed to use thinking and logic skills to figure out how many times the line 'sum++' will run, as a function of N. Hint: it runs once for every time that the third line is encountered.

How many times is the second line encountered?

Each time the second line is encountered, the value of 'i' is set. How many times does the third line run with that value of i? Therefore, how many times will it run overall? (Hint: if I give you a different amount of money on several different occasions, how do you find out the total amount I gave you?)

Each time the third line is encountered, the fourth line happens once.

Which line happens most often? How often does it happen, in terms of N?

So guess what interest you is the sum++ and how many time you execute it.

The final stat of sum would give you that answer.

Actually your loop is just:

Sigma(n) n goes from 1 to N.

Which equal to: N*(N+1) / 2 This give you in big-o-notation O(N^2)

Also beside the name of you question there is no worst case in you algorithm. Or you could say that the worst case is when N goes to infinity.

Using Sigma notation to represent your loops:

How to calculate worst case analysis of this algorithm?