这个基本算法O（n）怎么样？

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）次，第二个循环执行O（n）次是否给出O（n logn）？

Answer 1

O（ n ）意味着当输入大小为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是2的最小幂，不小于p-1小于2*n ，与n成正比，所以该程序仍然是O（ n ）。）