Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

algorithm - Running time complexity of double for-loops

I'm somewhat confused by the following algorithms. In particular, I don't understand why the first is O(n) and the second is O(n^2). My only intuition is perhaps that the inner and outer loops for the first algorithm aren't "linked." Secondly, I can intuitively see that the second algorithm is O(n^2), but how would we go about finding some constants c1, c2 to prove f(n) is big-0 and little-0 of n^2?

sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
    sum++;

sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        sum++;
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

To formally deduce the order of growth, you may proceed like the following:

enter image description here

For the c' case, the inner loop won't execute when i = 0, therefore, the solution is to externalize the outer loop "iterations" that won't affect the inner loop.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...