algorithm - 代码的Big-O复杂性

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

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

它没有常规主题，该如何计算？

最佳答案

其他答案给出的上限实际上过高。该算法具有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)。