我想计算这个嵌套 for 循环的复杂度:
s = 0;
for(i=1; i<=n; i*=2)
for(j=1; j<=i; j*=2)
s++;
我使用什么策略来找到这段代码的 Big O 复杂度?
最佳答案
外层循环执行 1, 2, 4, 8, ... n,这需要 O(lg n) 步,因为你只能加倍一个 O (lg n) 次,直到您击中 n。
内部循环做同样的事情。它只上升到 i,但是在外循环的最后一次迭代中,i 达到了它的最大值,又是 n,所以这是也为 O(lg n)。
将它们放在一起给出了 O((lg n)²) 的上限,通常缩写为 O(lg² n)。
关于for-loop - 计算嵌套for循环的复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15433435/