Order Of Growth 复杂的循环
Order Of Growth complicated for loops
对于下面的代码片段,N的增长顺序是什么?
int sum = 0;
for (int i = 1; i <= N; i = i*2)
for (int j = 1; j <= N; j = j*2)
for (int k = 1; k <= i; k++)
sum++;
我发现有 lgN 项,但我一直在评估这部分:lgN(1 + 4 + 8 + 16 + ....)。序列的最后一项是什么?我需要最后一项来计算总和。
你的外循环有一个几何级数,所以有一个封闭的形式,你想对它求和:
1 + 2 + 4 + ... + 2^N = 2^(N+1) - 1
准确的说,你的总和是
1 + ... + 2^(floor(ld(N))
其中 ld
表示以 2 为底的对数。
最外面的两个循环相互独立,而最里面的循环只依赖于i
。最内层循环只有一次操作(自增),也就是说访问最内层循环的次数等于求和结果。
\sum_i=1..( floor(ld(N)) ) {
\sum_j=1..( floor(ld(N)) ) {
\sum_k=1..2^i { 1 }
}
}
// adjust innermost summation bounds
= \sum_i=1..( floor(ld(N)) ) {
\sum_j=1..( floor(ld(N)) ) {
-1 + \sum_k=0..2^i { 1 }
}
}
// swap outer summations and resolve innermost summation
= \sum_j=1..( floor(ld(N)) ) {
\sum_i=1..( floor(ld(N)) ) {
2^i
}
}
// resolve inner summation
= \sum_j=1..( floor(ld(N)) ) {
2^(floor(ld(N)) + 1) - 2
}
// resolve outer summation
= ld(N) * N - 2 * floor(ld(N))
这相当于 Big-Oh 表示法中的 O(N log N)
(表达式中的第二项逐渐消失到第一项)。
根据我的理解,外层循环需要 log N
步,下一个循环也需要 log N
步,最内层循环最多需要 N
步(尽管这是一个非常粗略的界限)。总的来说,循环的运行时复杂度最多为 ((log N)^2)*N
,这可能会有所改进。
对于下面的代码片段,N的增长顺序是什么?
int sum = 0;
for (int i = 1; i <= N; i = i*2)
for (int j = 1; j <= N; j = j*2)
for (int k = 1; k <= i; k++)
sum++;
我发现有 lgN 项,但我一直在评估这部分:lgN(1 + 4 + 8 + 16 + ....)。序列的最后一项是什么?我需要最后一项来计算总和。
你的外循环有一个几何级数,所以有一个封闭的形式,你想对它求和:
1 + 2 + 4 + ... + 2^N = 2^(N+1) - 1
准确的说,你的总和是
1 + ... + 2^(floor(ld(N))
其中 ld
表示以 2 为底的对数。
最外面的两个循环相互独立,而最里面的循环只依赖于i
。最内层循环只有一次操作(自增),也就是说访问最内层循环的次数等于求和结果。
\sum_i=1..( floor(ld(N)) ) {
\sum_j=1..( floor(ld(N)) ) {
\sum_k=1..2^i { 1 }
}
}
// adjust innermost summation bounds
= \sum_i=1..( floor(ld(N)) ) {
\sum_j=1..( floor(ld(N)) ) {
-1 + \sum_k=0..2^i { 1 }
}
}
// swap outer summations and resolve innermost summation
= \sum_j=1..( floor(ld(N)) ) {
\sum_i=1..( floor(ld(N)) ) {
2^i
}
}
// resolve inner summation
= \sum_j=1..( floor(ld(N)) ) {
2^(floor(ld(N)) + 1) - 2
}
// resolve outer summation
= ld(N) * N - 2 * floor(ld(N))
这相当于 Big-Oh 表示法中的 O(N log N)
(表达式中的第二项逐渐消失到第一项)。
根据我的理解,外层循环需要 log N
步,下一个循环也需要 log N
步,最内层循环最多需要 N
步(尽管这是一个非常粗略的界限)。总的来说,循环的运行时复杂度最多为 ((log N)^2)*N
,这可能会有所改进。