Сколько раз будет выполнено это утверждение?

Question

Сколько раз будет выполняться этот оператор?

#include <stdio.h>

int main() {
    p = 0;
    for(i = 1; i < n; i = i * 2)
    {
       p++;
    }
    return 0;
}

Ответ должен быть log (n) , но я получаю log (n) +1 .

Answer 1

В случае сложности времени, а именно:

• 1 от p=0;
• от цикла for
• отвнутренняя часть цикла

в целом будет:

---

В случае значения p:

Чтобы доказать это, мы можем сказать, что p изначально 0 и увеличивается до тех пор, пока i меньше n.

Если мы предположим , у нас будет k1 и k2 до окончания цикла:

, поэтому p увеличивается на 1 для k1раз. Поэтому: p=k1 в конце. Мы знаем:

• 
• 
• 

Следовательно: