Big-O 嵌套循环
Big-O Nested Loops
试图理解大 O 和嵌套循环我一直在浏览笔记,但无法理解这个问题的嵌套循环部分是如何工作的...我的答案是 6 + 1.5n + nlogn 写道从讲座上下来,但不明白如何获得 n log n 部分
Simple Statement;
Simple Statement;
Simple Statement;
Simple Statement;
for ( int i = 0; i < ( n / 2 ); i++ ) {
Simple Statement;
Simple Statement;
Simple Statement;
}
Simple Statement;
Simple Statement;
for ( int i = 0; i < 2 * n; i++ ) {
for ( int j = 0; j < n; j = 2 * j ) {
Simple Statement;
Simple Statement;
}
}
我的理解是 6 来自不在循环内的六个语句,而 1.5n 来自 3(n-1 + n-2 +....1)/2 所以如果有人可以帮助最后一部分或纠正我,如果我错了,将不胜感激
我坚持的部分:
for ( int i = 0; i < 2 * n; i++ ) {
for ( int j = 0; j < n; j = 2 * j ) {
Simple Statement;
Simple Statement;
}
}
嗯,我猜,问题中有一个 错别字 ,内部循环应该是
// notice "j = 1", not "j = 0",
// otherwise you have an infinite loop, since 0 * 2 == 0
for (int j = 1; j < n; j = 2 * j )
在这种情况下,外循环
for (int i = 0; i < 2 * n; i++ )
带来2 * n
,而内在(注意j = 2 * j
)
for (int j = 1; j < n; j = 2 * j )
结果只有 log(n)
;最后(因为循环是嵌套的,我们应该增加复杂性)我们有
O(n * log(n))
从 0 to 2*n
迭代将导致 O(N)
的复杂度。从 0 to n
开始迭代,步数为 2 的幂,将导致复杂度为 O(log(N))
。将这 2 个复杂度相乘将得到 O(N * log(N))
的最终复杂度。
试图理解大 O 和嵌套循环我一直在浏览笔记,但无法理解这个问题的嵌套循环部分是如何工作的...我的答案是 6 + 1.5n + nlogn 写道从讲座上下来,但不明白如何获得 n log n 部分
Simple Statement;
Simple Statement;
Simple Statement;
Simple Statement;
for ( int i = 0; i < ( n / 2 ); i++ ) {
Simple Statement;
Simple Statement;
Simple Statement;
}
Simple Statement;
Simple Statement;
for ( int i = 0; i < 2 * n; i++ ) {
for ( int j = 0; j < n; j = 2 * j ) {
Simple Statement;
Simple Statement;
}
}
我的理解是 6 来自不在循环内的六个语句,而 1.5n 来自 3(n-1 + n-2 +....1)/2 所以如果有人可以帮助最后一部分或纠正我,如果我错了,将不胜感激
我坚持的部分:
for ( int i = 0; i < 2 * n; i++ ) {
for ( int j = 0; j < n; j = 2 * j ) {
Simple Statement;
Simple Statement;
}
}
嗯,我猜,问题中有一个 错别字 ,内部循环应该是
// notice "j = 1", not "j = 0",
// otherwise you have an infinite loop, since 0 * 2 == 0
for (int j = 1; j < n; j = 2 * j )
在这种情况下,外循环
for (int i = 0; i < 2 * n; i++ )
带来2 * n
,而内在(注意j = 2 * j
)
for (int j = 1; j < n; j = 2 * j )
结果只有 log(n)
;最后(因为循环是嵌套的,我们应该增加复杂性)我们有
O(n * log(n))
从 0 to 2*n
迭代将导致 O(N)
的复杂度。从 0 to n
开始迭代,步数为 2 的幂,将导致复杂度为 O(log(N))
。将这 2 个复杂度相乘将得到 O(N * log(N))
的最终复杂度。