Какова временная сложность следующего фрагмента кода?

Question

int a = 0, i = N; 
while (i > 0) { 
 a += i; 
 i /= 2; 
}

По моему мнению, сложность должна быть O (N / 2), но ответ O (logN). Может ли кто-нибудь помочь мне понять это?

Answer 1

Ваше предположение легко опровергается простым примером. Давайте предположим, N = 32. Итерации выглядят следующим образом:

1: i = 32
2: i = 16
3: i = 8
4: i = 4
5: i = 2
6: i = 1
7: i = 0 (loop aborted)

Это дает счетчик итераций 6, тогда как ваше предположение будет 32/2 = 16. Я предполагаю, что вы думаете об этом, что i уменьшается вдвое, но вместо этого он уменьшается вдвое при каждой итерации, что делает его O(log(n)).