一块代码的大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
内循环迭代的总数在n和2n之间，即它是Θ（n）。
你总是假设你得到了每个级别最差的情况。
现在，你迭代一个有N个元素的数组，所以我们从O(N)开始。
现在让我们说你的i总是等于X和X总是偶数（记住，每一次最坏的情况）。
你需要多less次将X除以2得到1 ？ （这是偶数停止分裂的唯一条件，当它达到1时）。
换句话说，我们需要求解X/2^k = 1和k=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)是基数2中n的位数的总和，因此可忽略不计（至多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）。
