Big-O 嵌套循环

Question

试图理解大 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;
         } 
        }

Answer 1

嗯，我猜，问题中有一个 错别字 ，内部循环应该是

// 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))

Answer 2

从 0 to 2*n 迭代将导致 O(N) 的复杂度。从 0 to n 开始迭代，步数为 2 的幂，将导致复杂度为 O(log(N))。将这 2 个复杂度相乘将得到 O(N * log(N)) 的最终复杂度。

Big-O 嵌套循环

Big-O Nested Loops

algorithm

data-structures

big-o

nested-loops

big-theta