一块代码的大O复杂性

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

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

我尝试了一些数字的algorithm。 我得到了不同的结果。 例如,如果n = 6,则该algorithm输出如下所示

 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 

它没有一个固定的主题,我应该怎么计算呢?

其他答案给出的上限实际上太高了。 这个algorithm有一个O(n)运行时间,它比O(n * logn)更紧的上界。

certificate:我们来计算内循环将执行多less次迭代。

外循环运行n次。 内部循环至less为每一个运行一次。

  • 即使i ,内部循环运行至less两次。 这发生n/2次。
  • 对于i可以被4整除,内部循环至less运行三次。 这发生n/4次。
  • 对于i可以被8整除,内部循环至less运行四次。 这发生n/8次。

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

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

内循环迭代的总数在n2n之间,即它是Θ(n)。

你总是假设你得到了每个级别最差的情况。
现在,你迭代一个有N个元素的数组,所以我们从O(N)开始。
现在让我们说你的i总是等于XX总是偶数(记住,每一次最坏的情况)。
你需要多less次将X除以2得到1 ? (这是偶数停止分裂的唯一条件,当它达到1时)。
换句话说,我们需要求解X/2^k = 1k=log<2>(X)的方程,这使得我们的algorithm取O(n log<2>(X))这些步骤可以简单地写成O(nlog(n))

对于这样的循环,我们不能分开内循环和外循环的计数 – >variables被紧缩!

因此,我们必须计算所有步骤。

实际上,对于外循环(在i )上的每一次迭代,我们都会有

 1 + v_2(i) steps 

其中v_2是2-adic估值(参见例如http://planetmath.org/padicvaluation ),它对应于i素因子分解中的2的幂。

所以,如果我们为所有i添加步骤,我们会得到以下步骤的总数:

 n_steps = \sum_{i=1}^{n} (1 + v_2(i)) = n + v_2(n!) // since v_2(i) + v_2(j) = v_2(i*j) = 2n - s_2(n) // from Legendre formula (see http://en.wikipedia.org/wiki/Legendre%27s_formula with `p = 2`) 

然后我们看到步骤数量 正好是

 n_steps = 2n - s_2(n) 

由于s_2(n)是基数2n的位数的总和,因此可忽略不计(至多log_2(n)因为基数2数字是0或1,并且至多有log_2(n)数字) n

所以你的algorithm的复杂性等价于n

 n_steps = O(n) 

不是许多其他解决scheme中提到的O(nlog(n)) ,而是更小的数量!

让我们从最坏的情况开始:

如果你不断地用2(整数)分隔,你不需要停止,直到你达到1为止。基本上取决于比特宽度的步数是用2的对数找出来的。 所以内部是log n。 外部显然是n,所以N log N总和。

一个do循环减半,直到k变成奇数。 k最初是j的副本,它是i的副本,因此运行1 + 2幂除以i

  • 我= 1是奇数,所以它通过do循环1,
  • 我= 2除以2,所以1 + 1,
  • 我= 4分2次,所以1 + 2等

这使最多1 +日志(我) do处决(以2为底的对数)。

for循环从1到n迭代i ,所以上界是n (1 + log n),即O(n log n)。