Big-O符号检查理解

Question

我想检查一下我对Big-O表示法的理解.如果我有代码:

 for(int bound = 1; bound <= n; bound *= 2){
      for( int i = 0; i < bound; i++) {
            for(int j = 0; j < n; j += 2){
                   .....Code
            }
            for(int j = 1; j < n; j *= 2){
                   ......Code
            }
      }
 }

这个N ³的Big-O表示法？

Answer 1

不完全的.外循环增量为bound *= 2,因此循环为O(log n).两个内部循环(i和第一个j循环)都是O(n),因此当嵌套时它们是O(n ²).(您可以忽略j *= 2内部循环,因为它比j += 2循环更快,并且不会显着影响程序的运行时间.)

把这一切放在一起,整个程序是O(log n*n ²).