algorithm - これの最悪の場合の時間計算量は何でしょうか？

Question

for(int i = 1 ; i < n ; i* = 2)
for(int j = 1 ; j < i ; j* = 2)

誰かが私にこれを説明できますか？そうだと思いますがlog(n)*log(i)、正しいですか？

Answer 1

仮定

for (i = 1; i < n; i *= 2)
   for (j = 1; j < i; j *= 2)
      ...stuff...

「stuff」は 1 + 2 + 3 + ... + log(n)-1 回実行されます。1 から N までの整数の合計は N * (N + 1) / 2 であるため、最悪の場合の実行時間は O(log(n) ^ 2) になります。