algorithm - 一段代码的大O复杂度

Question

我在算法设计中有一个关于复杂性的问题。在这个问题中给出了一段代码，我应该计算这段代码的复杂性。 伪代码是:

for(i=1;i<=n;i++){
    j=i
    do{
        k=j;
        j = j / 2;
    }while(k is even);
}

我对一些数字尝试了这个算法。我得到了不同的结果。例如，如果 n = 6，则此算法输出如下所示

i = 1 -> executes 1 time
i = 2 -> executes 2 times
i = 3 -> executes 1 time
i = 4 -> executes 3 times
i = 5 -> executes 1 time
i = 6 -> executes 2 times

它没有固定的主题，我该如何计算？

Answer 1

其他答案给出的上限实际上太高了。该算法具有 O(n) 运行时间，这是一个比 O(n*logn) 更严格的上限。

证明:让我们数一数内部循环将执行的总迭代次数。

外循环运行 n 次。内部循环至少为其中的每一个运行一次。

• 即使是i，内部循环也至少运行两次。这种情况发生了 n/2 次。
• 对于能被4整除的i，内层循环至少运行3次。这发生了 n/4 次。
• 对于能被 8 整除的 i，内循环至少运行四次。这种情况发生了 n/8 次。
• ...

所以内循环运行的总次数是:

n + n/2 + n/4 + n/8 + n/16 + ... <= 2n

内循环迭代总量在n和2n之间，即为Θ(n)。