大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.它是一個無限循環。