嵌套循环渐近分析

Question

需要帮助解决这个硬件示例。该示例说明 0(n) 运行时间。我看到外循环是 O(logn) 我不知道如何描述与 n 有关的内部循环。非常感谢您的帮助。

for (int i = 1; i <= N; i = i*2) // log n 
    for (int j = 0; j < i; j++)  // less than n i don't know how to describe the growth
        sum++;

答案:: 0(n)

Answer 1

内循环是O(n)时间，因为它会遍历每个元素一次。如果i为1000，则1000次，如果i为10000，则10000次等

Answer 2

最简单的方法可能是分析运行代码段在聚合中的时间。在外循环的第一次迭代中，内循环将运行一次。在外循环的第二次迭代中，内循环将运行 2 次。在外循环的第三次迭代中，内循环将运行 4 次。更一般地，在外循环的第 k 次迭代中，内循环将运行 2^k 次。一旦 i 变得大于 N，外循环就会停止，这发生在 log₂ N 次迭代之后。

如果我们总结完成的总工作量，我们会发现它是

1 + 2 + 4 + 8 + ... + 2^{log₂ N} = 2^{log₂ N + 1} - 1 = 2n - 1

（这使用了 1 + 2 + 4 + 8 + ... + 2^k = 2^k+1 - 1).因此，整段代码（即包括两个循环）的总工作量为 O(n)。

嵌套循环渐近分析

Nested Loops Asymptotic analysis

algorithm

big-o

loops

time-complexity