3 个循环的 Hard Big O 复杂度
Hard Big O complexity for 3 loops
我尝试计算此代码的 Big O 复杂度，但我总是失败....
我尝试嵌套 SUM 或获取每个案例的步数，例如：
- i=1 j=1 k=1（1 步）
- i=2 j=1,2 k=1,2,3,4（4 步）
- 。 . . . . . . . . . . . . . .
- i=n（我说 n = 2^(log n) j = 1,2,4,8,16,.....,n k=1,2,3,4,... ..n^2（n^2 步）
然后将所有步骤汇总在一起，我需要帮助。
for (int i=1; i<=n; i*=2)
for (int j=1; j<=i; j*=2)
for(int k=1; k<=j*j; k++)
//code line with complexity code O(1)
For the outermost loop:
sum_{i in {1, 2, 4, 8, 16, ...}} 1, i <= n (+)
<=>
sum_{i in {2^0, 2^1, 2^2, ... }} 1, i <= n
Let 2^I = i:
2^I = i <=> e^{I log 2} = i <=> I log 2 = log i <=> I = (log i)/(log 2)
Thus, (+) is equivalent to
sum_{I in {0, 1, ... }} 1, I <= floor((log n)/(log 2)) ~= log n (*)
Second outermost loop:
sum_{j in {1, 2, 4, 8, 16, ...}} 1, j <= i (++)
As above, 2^I = i, and let 2^J = j. Similarly to above,
(++) is equivalent to:
sum_{J in {0, 1, ... }} 1, J <= floor((log (2^I))/(log 2)) = floor(I/(log 2)) ~= I (**)
To touch base, only the outermost and second outermost
have now been reduced to
sum_{I in {0, 1, ... }}^{log n} sum_{J in {0, 1, ...}}^{I} ...
Which is (if there would be no innermost loop) O((log n)^2)
Innermost loop is a trivial one if we can express the largest bound in terms of `n`.
sum_{k in {1, 2, 3, 4, ...}} 1, k <= j^2 (+)
As above, let 2^J = j and note that j^2 = 2^(2J)
sum_{k in {1, 2, 3, 4, ...}} 1, k <= 2^(2J)
Thus, k is bounded by 2^(2 max(J)) = 2^(2 max(I)) = 2^(2 log(n) ) = 2n^2 (***)
结合(*)、(**)和(***)，三个嵌套循环的渐近复杂度为：
O(n^2 log^2 n)（或者，O((n log n)^2)）。
我们看一下内循环运行的次数：j<sup>2</sup>。但是 j 以 2 的幂递增到 i。 i 依次递增 2 的幂直到 n。因此，让我们 "draw" 一张总和项的小图形，它会给出迭代总数：
---- 1
^ 1 4
| 1 4 16
log<sub>2</sub>(n) ...
| 1 4 16 ... n2/16
v 1 4 16 ... n2/16 n2/4
---- 1 4 16 ... n2/16 n2/4 n2
|<------log<sub>2</sub>(n)------>|
图形可以这样解释：i的每个值对应一行。 j 的每个值都是该行中的一列。数字本身就是 k 经历的迭代次数。 j 的值是数字的平方根。 i 的值是每行中最后一个元素的平方根。所有数字的总和就是迭代的总次数。
看最后一行，总和的项是(2<sup>z</sup>)<sup>2</sup> = 2<sup>2z</sup> 对于 z = 1 ... log<sub>2</sub>(n)。项在总和中出现的次数由列的高度调制。给定项的高度是 log<sub>2</sub>(n) + 1 - z（基本上是从 log<sub>2</sub>(n)).
所以最后的总和是
log2(n)
Σ 22z(log2(n) + 1 - z)
z = 1
以下是 Wolfram Alpha 对求和的评价：http://m.wolframalpha.com/input/?i=sum+%28%28log%5B2%2C+n%5D%29+%2B+1+-+z%29%282%5E%282z%29%29%2C+z%3D1+to+log%5B2%2C+n%5D:
C1n2 - C2log(n) - C3
去掉所有不重要的项和常数，结果是
O(n2)
我尝试计算此代码的 Big O 复杂度，但我总是失败....
我尝试嵌套 SUM 或获取每个案例的步数，例如：
- i=1 j=1 k=1（1 步）
- i=2 j=1,2 k=1,2,3,4（4 步）
- 。 . . . . . . . . . . . . . .
- i=n（我说 n = 2^(log n) j = 1,2,4,8,16,.....,n k=1,2,3,4,... ..n^2（n^2 步）
然后将所有步骤汇总在一起，我需要帮助。
for (int i=1; i<=n; i*=2)
for (int j=1; j<=i; j*=2)
for(int k=1; k<=j*j; k++)
//code line with complexity code O(1)
For the outermost loop:
sum_{i in {1, 2, 4, 8, 16, ...}} 1, i <= n (+)
<=>
sum_{i in {2^0, 2^1, 2^2, ... }} 1, i <= n
Let 2^I = i:
2^I = i <=> e^{I log 2} = i <=> I log 2 = log i <=> I = (log i)/(log 2)
Thus, (+) is equivalent to
sum_{I in {0, 1, ... }} 1, I <= floor((log n)/(log 2)) ~= log n (*)
Second outermost loop:
sum_{j in {1, 2, 4, 8, 16, ...}} 1, j <= i (++)
As above, 2^I = i, and let 2^J = j. Similarly to above,
(++) is equivalent to:
sum_{J in {0, 1, ... }} 1, J <= floor((log (2^I))/(log 2)) = floor(I/(log 2)) ~= I (**)
To touch base, only the outermost and second outermost
have now been reduced to
sum_{I in {0, 1, ... }}^{log n} sum_{J in {0, 1, ...}}^{I} ...
Which is (if there would be no innermost loop) O((log n)^2)
Innermost loop is a trivial one if we can express the largest bound in terms of `n`.
sum_{k in {1, 2, 3, 4, ...}} 1, k <= j^2 (+)
As above, let 2^J = j and note that j^2 = 2^(2J)
sum_{k in {1, 2, 3, 4, ...}} 1, k <= 2^(2J)
Thus, k is bounded by 2^(2 max(J)) = 2^(2 max(I)) = 2^(2 log(n) ) = 2n^2 (***)
结合(*)、(**)和(***)，三个嵌套循环的渐近复杂度为：
O(n^2 log^2 n)（或者，O((n log n)^2)）。
我们看一下内循环运行的次数：j<sup>2</sup>。但是 j 以 2 的幂递增到 i。 i 依次递增 2 的幂直到 n。因此，让我们 "draw" 一张总和项的小图形，它会给出迭代总数：
---- 1 ^ 1 4 | 1 4 16log<sub>2</sub>(n)... | 1 4 16 ... n2/16 v 1 4 16 ... n2/16 n2/4 ---- 1 4 16 ... n2/16 n2/4 n2 |<------log<sub>2</sub>(n)------>|
图形可以这样解释：i的每个值对应一行。 j 的每个值都是该行中的一列。数字本身就是 k 经历的迭代次数。 j 的值是数字的平方根。 i 的值是每行中最后一个元素的平方根。所有数字的总和就是迭代的总次数。
看最后一行，总和的项是(2<sup>z</sup>)<sup>2</sup> = 2<sup>2z</sup> 对于 z = 1 ... log<sub>2</sub>(n)。项在总和中出现的次数由列的高度调制。给定项的高度是 log<sub>2</sub>(n) + 1 - z（基本上是从 log<sub>2</sub>(n)).
所以最后的总和是
log2(n) Σ 22z(log2(n) + 1 - z) z = 1
以下是 Wolfram Alpha 对求和的评价：http://m.wolframalpha.com/input/?i=sum+%28%28log%5B2%2C+n%5D%29+%2B+1+-+z%29%282%5E%282z%29%29%2C+z%3D1+to+log%5B2%2C+n%5D:
C1n2 - C2log(n) - C3
去掉所有不重要的项和常数，结果是
O(n2)