Временная сложность 'for (i = m; i> n; i / = 2)'

Question

Какова временная сложность этого?:

for(i=m; i>n; i/=2)

Предположим, что цикл останавливается при i <= n. <br>Затем выполняется остановка цикла при i = n.
i равно m / 2 ^ k
То есть m / 2^ k = n, когда цикл останавливается.
Что за биг-о нотация для этого?

Answer 1

Представьте себе, что m=16.Тогда каждая итерация i будет делиться пополам, округляя: 16, 8, 4, 2, 1, 0, 0 ...

Напомним, что log2(x) является логарифмом основания 2.Итак, log2(2) = 1, log2(4) = 2, log2(8) = 3 и так далее.Удвоение числа увеличивает значение log2 на 1. Уменьшение вдвое числа уменьшает его на 1.

Это означает, что каждый шаг вашего цикла будет уменьшать значение log2 на 1, пока не достигнет n.

Сколько шагов нужно, чтобы добраться от m до n?Это ваш ответ.