对嵌套循环的时间复杂度和寻找技巧感到困惑 [英] Confused about the time complexity of nested loops and looking for tips

问题描述

让我们说我有两个代码:

Lets say I have two codes:

代码A:

for i = 0;
for j = 0;
while(i<n){       // O(n)
    while(j<n){   // O(n)
       printf("hello");
       .....

运行时间= o(n)x O(n)= O(n ^ 2)..

代码B:

int result = 0;
int i = 0;
while (i < n/2){    //O(n)
result += arr[i];
i += 1;
    while(i >= n/2 && i < n){   //O(n)
        results += arr[i];
        i +=1;
        }

运行时间= O(n)

对于代码B，我们为什么不像对代码A那样将两个O(n)相乘以得到O(n ^ 2)?对于如何确定运行时间感到非常困惑.

推荐答案

让我们在脑海中运行一段代码B:

Let's give a run of code B in our head:

假设n很大，例如至少为100.最初我们有i = 0，因此外循环的条件为true，由于第5行，i随后将增加1. (i += 1).因此，在这一点上我们有i = 1，但是在这种情况下，条件是内部循环为false，因此我们继续进行下一轮外部循环.

Suppose that n is quite large, say at least 100. Initially we have i = 0, so the condition for the outer loop is true, i will then increase by 1 due to line 5 (i += 1). So at this point we have i = 1, however in this case the condition the inner loop is false, so we just continue to the next turn of the outer loop.

在i变为n/2 - 1之前，外循环和内循环的条件分别保持为true和false，在此阶段，外循环的条件为true，依此类推i增加到n /2，在这种情况下，内部循环的条件也变为true.因此，i将通过内部循环增加到n.

The conditions for the outer loop and the inner loop remain to be true and false respectively until i becomes n/2 - 1, at this stage, the condition for the outer loop is true, and so i increases to n /2, and in this case the condition for the inner loop becomes true as well. So i will be increased up to n by the inner loop.

最后，我们有了i = n，循环的条件都为false，并且不会进一步循环.

At last, we have i = n, the conditions for the loops are both false, and it will not loop further.

所以复杂度如下:

i          Work done
------------------------
0          1
1          1
2          1
.          .
.          .
.          .
n/2-2      1
n/2-1      n/2 + 1

所以总的工作是:

(1 + n/2 - 2) * 1 + 1 * (n/2 + 1) = O(n)

这篇关于对嵌套循环的时间复杂度和寻找技巧感到困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！