почему этот ответ на эту проблему анализа сложности времени?

Question

задание говорит, определите O, Ω, Θ для следующего кода:

void f1(int n) {
 int i;
 for (i = n; i > 0; i /= 2) {
 printf("%d\n", i % 2);
 }
}

Хорошо, я знаю, что цикл будет повторяться, пока я не стану 0, поэтому я буду n, n / 2,n / 4 n / 8 ... 2 / 2,0,

Я посмотрел в решениях, и ответ на проблему O (log n), Ω (log n), Θ (log n),

Почему журнал ответов n?

Любая помощь очень ценится!

Answer 1

Обратите внимание: Цикл для завершается, когда i == 0.

Теперь значение i уменьшается путем его деления на 2, поэтому предположим, что после некоторых k + 1 делений на 2 значение i станет равным 0. Это означает, что цикл выполняется k раз и затем завершается.

Теперь вы можете сказать, что i = n / (2 ^ k) до завершения цикла.

Примечание: здесь (2 ^ k) означает 2 в степени k.

И до того, как цикл завершится в i == 0последнее выполнение цикла будет в i = 1.

Следовательно, n / (2 ^ k) = 1.

Перенос знаменателя на другую сторону, n= (2 ^ k)

Взяв лог-базу 2 с обеих сторон, log2 (n) = log2 (2 ^ k) = k

Следовательно, k = log2 (n) и какk - количество выполнений цикла, сложность по времени O (Log2 (n)) и игнорирование констант, т.е. base 2 , O (Log (n)).