我在算法设计方面有一个关于复杂度的问题。给定了一段代码，我需要计算该代码的复杂度。
伪代码如下：
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
它没有一个固定的主题，我应该如何计算它？
n + n/2 + n/4 + n/8 + n/16 + ... <= 2n
内层循环迭代的总次数在n和2n之间，即它是Θ(n)。
O(N)开始。i始终等于X，而且X始终为偶数（记住，每次都是最坏情况）。X除以2多少次才能得到1？（当偶数除以2达到1时，这是唯一停止除法运算的条件）X/2^k = 1 ，其中 X=2^k 并且 k=log<2>(X)
这使得我们的算法需要O(n log<2>(X))步骤，可以轻松写成 O(nlog(n))。n 次且内层循环的最坏情况复杂度为 O(log(n))，但并不能得出总体复杂度为 O(n log(n)) 的结论；这取决于内层循环的最坏情况随着 i 从 1 到 n 改变的频率。我猜测这个频率不是 O(n)，实际总体复杂度更低（也许是 O(log(n)^2)）。 - Ted Hoppi 上具有最坏情况下 O(log(i)) 的行为，并且对于所有其他值都是 O(1)。那么外部循环执行 n 次并不会导致总体复杂度为 O(n log(n))；它将是 O(n) + O(log(n)) = O(n)。当然，实际的内部循环没有这种极端的行为，但我认为最坏情况密度是否支持 O(n log(n)) 的结论还远未明确。 - Ted Hopp对于这样的循环，我们无法分离内部循环和外部循环的计数 -> 变量是紧密相连的！
因此，我们必须计算所有步骤。
实际上，对于每次外部循环（在 i 上），我们会有
1 + v_2(i) steps
其中v_2是2进制估值（例如：参见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)
作为n在二进制中各位数字之和的总和的s_2(n)是可以忽略不计的, 最多只有 log_2(n) 的数量级，因为在二进制中每一位数字都是0或1，而且最多只有log_2(n)个数字。
因此，您的算法复杂度与n等价:
n_steps = O(n)
这个问题的时间复杂度并不是像其他解决方案中所述的O(nlog(n))，而是更小的一个数量级！
1 + Omega(n)，其中Omega(n)返回质因数的数量，例如6 = 2,3，因此它不是n +... 而是n logn。我认为您错过了第1行的for循环？ - Alexander Holman让我们从最坏的情况开始：
如果你一直用2（整数）除下去，直到得到1为止，你就不需要停止。基本上，步骤的数量取决于位宽度，这是通过使用二进制对数来发现的。因此内部部分是log n。外部部分显然是n，所以总共是N log N。
一个do循环将j减半，直到k变成奇数。 k最初是j的副本，j是i的副本，因此do运行1 +除以i的2的幂次方：
do循环一次，这使得最多有1 + log（i）个do执行（以2为底的对数）。
for循环从1到n迭代i，因此上限是n次（1 + log n），即O（n log n）。
n... 请看我的回答或者 @interjay 的！ - Samuel Caillerie