一段代码的大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

你总是假设你在每个级别遇到最坏的情况。
现在，你遍历一个包含 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))

Answer 2

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

如果你一直除以 2（整数），你不需要停下来，直到你到达 1. 基本上使步数取决于位宽，你用两个的对数找到的东西。所以内部是log n。外面的部分显然是 n，所以 N log N 总数。

Answer 3

A do 循环减半 j 直到 k 变为奇数。 k 最初是 j 的副本，后者是 i 的副本，因此 do 运行 1 + 2 的幂，除以 i：

i=1 是奇数，所以它使 1 通过 do 循环，
i=2除以2一次，所以1+1,
i=4 两次除以 2，所以 1+2，等等

最多执行 1+log(i) do 次（以 2 为底的对数）。

for循环从1到n迭代i，所以上限是n次(1+log n)，也就是O(n log n).

Answer 4

其他答案给出的上限实际上太高了。该算法具有 O(n) 运行时间，这是比 O(n*logn) 更严格的上限。

证明：让我们数一数内部循环将执行的总迭代次数。

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

对于偶数i，内循环至少运行两次。这种情况发生 n/2 次。
对于i能被4整除，内循环至少运行3次。这种情况发生 n/4 次。
对于i能被8整除，内循环至少运行四次。这种情况发生 n/8 次。
...

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

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

内循环迭代总量在n和2n之间，即为Θ(n)。

Answer 5

对于这样的循环，我们不能将内循环和外循环的计数分开 -> 变量是紧的！

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

事实上，对于外循环的每次迭代（在i），我们将有

1 + v_2(i) steps

其中 v_2 是 2-adic 估值（参见示例：http://planetmath.org/padicvaluation），它对应于 [=14= 的质因数分解中 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)是n的基数2的数字之和，可以忽略不计（至多log_2(n)，因为基数2 是 0 或 1，因为最多 log_2(n) 位）与 n.

相比

所以你算法的复杂度相当于n:

n_steps = O(n)

这不是许多其他解决方案中提到的O(nlog(n))但数量较少！

一段代码的大O复杂度

Big-O complexity of a piece of code

algorithm

time-complexity