时间复杂度n ^ 2

Question

这是O（N ^ 2）还是O（nlogn）。有嵌套循环时，它不是n ^ 2吗？

int a[], N;
int f1(){ int i, j, sum=0;
    for (i=1;; i=2*i)
    {
        If (i>=N)  return sum;
        for (j=1; j<2*i;j++) sum+=a[i];
    }

Answer 1

这是O(N log N)因为外循环i在每次迭代中将值翻倍。因此，外环的复杂性O(log N)，而不是O(N)。

如果您有i++或类似的代替，i=2*i则两个循环的时间复杂度将会是O(n^2)。

编辑：这是一个简化的分析。请参阅R Sahu的答案，以进行更严格的分析。