这段代码的复杂度是多少

Question

我必须确定这段代码的大 O 复杂性。我认为答案是 nlogn 但显然是 n。谁能帮忙解释一下为什么会这样？

void funct(int n)
{
    for (int i = n; i > 0; i /= 2)
        for(int j = 0; j < i; j++)
            printf("%d\n", j%2);
}

Answer 1

外循环，我相信你可以看到，它执行了 log(n) 次。内循环平均执行 log(n)/2 次。因此 printf 语句被执行 log(n) * (log(n) / 2) 次，等于 n / 2。所以代码的复杂度是O(n).

Answer 2

这是几何级数第一次内循环执行n次。第二次执行n/2次。 ETC... 所以我们有顺序： n + n/2 + n/4 + ... + 1 所以最后的公式是：

n*(1 - (1/2)^(log n))/(1/2)

相当于n

Answer 3

看这些可以使用双西格玛解决：让$代表sigma。所以这个问题是：

$(i=n downto 0 by a factor of 2 )$(j=0 to i-1) 1

其中 1 表示单位成本

现在对于内西格玛它的总和是 1 i 倍 = i

现在的问题是 $(i=n downto 1 by a factor of 2 ) i

这是 i 值的总和，即 n+n/2+n/4+...+1(when n/2^x=1 or after log(n) terms)+0

或 n*(1+1/2+.....log(n) terms)

这是收敛的Geometric progression。结果将是 n*(1 - (1/2)^(log n))/(1/2) 即 O(n)

What is the complexity of this piece of code