这个基本算法O(n)怎么样？

Question

int G(int a[], int n) {
int x=0, i, j;

 for(i=1; i<n; i=i*2){
 for(j=0; j<i; j++)
     x += a[j];
 }
 return x;
}

该算法的最坏情况如何严格限制 O(n)。是否第一个循环未执行 O(log(n) 次，第二个 for 循环执行 O(n) 次，给出 O(n logn)？

Answer 1

O(n) 表示当输入大小为 n。在此表征中，内部循环为 O(n)，但其输入大小为 i，因此它需要一些与 i 成比例的步数。

累加执行了多少次内循环迭代。如果n恰好是2的幂，即1 + 2 + 4 + 8 + … + n/2。该系列的总和是 n-1。因此，当其输入大小为 n 时，整个程序将执行 n-1 次迭代。所以它是 O(n).

(如果n不是恰好2的幂，则迭代次数为p-1，其中p为不小于[=12=的最小2的幂].p-1小于2*n，与n成正比，所以程序还是O(n).)