入れ子のforループの実行時間はO（n^2）ですか？

Question

私は外側のループは少し私をオフにスローこれらのネストされたループ

int sum = 0; 
for (int n = N; n > 0; n = n/2) { 
    for (int i = 0; i < n; i++) { 
     sum++; 
    } 
} 

を持っています。 ランタイムはまだO（n^2）ですか、それとも別のものですか？

Answer 1

ここで、内部ループは1 + 2 + ... + n/2 + n回実行します。 これは、このシーケンスではng個の項を持ち、int i = 0はlg回ng回実行することを意味します。

内部ループ内のステートメントの合計は2nです。 だから我々は外側のループが何回実行んO（N + LGのN）= O（n）の