Big-O嵌套循环

Question

试图理解Big 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))