大O符号为下面的循环

Question

会有什么代码的这些部分的大哦：

int sum = 0; 

for(int i = 1; i < N; i *= 2) 

for(int j =0; j <i; j++) 

sum++; 

而且

int sum = 0; 

for(int i = 0; i < N; i *= 2) 

for(int j =0; j <i; j++) 

sum++; 

我尝试： 据我都有时间复杂度等于至O （n^2），因为这里我们将n乘以n等于n^2。我对么？或者犯了一些错误？

Answer 1

对于代码的第一部分：

第一循环将从1到n，其中变量i会作为 1，2，4，8，16 ....Ñ 和在第二环路Ĵ从0至i所以时间复杂性将是

O（1 + 2 + 4 + 8 + 16 .... N）= O（2N - 1）= O（N）

和作为对于代码的第二部分

我从0开始，它总是为0，因为你在乘以它由2.它是一个无限循环。