一段代码的大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.
• 对于i4可整除,内循环至少运行三次.这种情况发生了n/4.
• 对于i8可整除,内循环至少运行四次.这种情况发生了n/8.
• ...

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

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

内循环迭代的总量在n和之间2n,即它是Θ(n).

Answer 2

你总是假设你得到了每个级别中最糟糕的情况.
现在,你迭代一个包含N个元素的数组,所以我们O(N)已经开始了.
现在让我们说你i的总是等于X并且X总是均匀(记住,每次最坏的情况).
多少次,你需要划分X由2获得1？(当偶数达到1时,这是偶数停止除法的唯一条件).
换句话说,我们需要解决的方程 X/2^k = 1是X=2^k和k=log<2>(X) 这使得我们的算法采取O(n log<2>(X))的步骤,它可以伊斯利可以写成O(nlog(n))