我如何确定这段代码中最坏的情况？

Question

for(i=1;i<=n;i++) {
        
    if((i&(i-1))==0) {      
        
        for(j=1;j<=i;j++) {
            f();
        }
    } else {
        f();
    }
    
}

我对这段代码做了一些测试用例，当 i = 2^(i-1) 执行第二个 for 时，我怎么能确定大 O 符号，我认为它可能是 O(n^2) . f() 是 O(1)，我怎样才能得到摊销分析

Answer 1

考虑 (i&(i-1)) == 0。这仅适用于 2 的幂（更多详细信息请参阅 this post）。小于 n 的 2 有多少次方？ log(n)。对于 log(n) 种情况，将第二个循环迭代 i 次，剩下的成本是 Theta(1)。因此，时间复杂度为（w.l.o.g。假设n是2的幂）：

T(n) = n - log(n) // for i != 2^k
       + (1 + 2 + 2^2 + ... + 2^{log(n)}) // for i = 2^k
     = n - log(n) + 2^{log(n)+1} - 1 = 3n - log(n) - 1 = Theta(n) // 2^log(n) = n

因此T(n) = Theta(n).

Answer 2

答案是n。

表达式( i & ( i - 1 ) ) == 0 )只有当i是2的幂时才为真。因此，它将执行log2( n )次。

下一步是找出从内部循环调用 f 的次数。 i 值是 2 的幂，它们的总和称为“几何级数”，维基百科 has the formula。

去掉一些常数，几何和与 2^N 成正比，其中 N 是系列中元素的数量。在你的例子中，计数是 log2( n ), 2^log2( n ) == n.

else 块也将被调用 O(n) 次。

Answer 3

所以我实际测试了这个，它是 n 是有道理的，因为你以 log(n) 的速率击中 2 的幂，但每次你击中一个时它就会爆炸按 2^n 输出。当它不是2的幂时，它也是n。

这是我运行:

#include <iostream>
#include <string>

int main()
{
    int n = 1000000;
    int count = 0;
    for(int i=1;i<=n;i++){
            
        if((i&(i-1))==0){       
            
            for(int j=1;j<=i;j++){
                count++;
                std::cout << i << "," << j << ":" << count << std::endl;
            }
        }else{
                count++;
                std::cout << i << ":" << count << std::endl;
        }
    
}}

所选值：

10:21

100:220

1000:2013

10000:26369

100000:231054

1000000:2048555

我并不是说运行该程序是确定的答案，只是它是一个有用的检查，您是否没有完全关闭（例如，如果它是 n^2 或常数时间）。如您所见，每次将输入放大 10 倍时，它或多或少都会对输出产生同样的影响。如果它是 n^2，那么最后一行将比第一行大 10^10。如果它是常数，它将是与第一个相似的数字。 nlogn 约1.1M次。

Answer 4

当 i 是 2 的幂时，内循环恰好执行对 f 的 i 次调用。否则，只有一个调用。

如果n是2的幂，设2^m，我们一共有

1 + 2 + 4 + ... n + n - m

来电，这是

3n - 1 - lg(n).

平均而言（主循环的每次迭代），这渐近于 3。

现在如果 n = 2^m + n' 和 n' < 2^m，计数是

1 + 2 + 4 + ... + 2^m + 2^m + n' - m = 3.2^m - 1 + n' - m = 3.n - 2.n' - 1 - Lg(n - n')

仍然摊销 3 更糟，但下降到 2 一些 n。

我如何确定这段代码中最坏的情况？

How could I determine the worst case in this code?

algorithm

analysis