Блог

Главная - Вопросы по программированию - Какова была бы временная сложность этого, когда i удваивается на каждой итерации?

Какова была бы временная сложность этого, когда i удваивается на каждой итерации?

#algorithm #time-complexity #big-o

#алгоритм #временная сложность #big-o

Вопрос:

 int i = 1;
while(i < N) {
  i *= 2;
}

Поскольку мы посещаем 1,2,4,8,16…(Квадраты). Я думаю, что временная сложность big-O должна быть O (log n). Правильный ли ответ? Правильно ли то, как я пришел к решению?

Комментарии:

1. Да, рассуждения верны. Однако вам следует избегать говорить int , потому что тогда вы попадаете на территорию переполнения.

Ответ №1:

Да, ваш ответ правильный. Вообще говоря, если значение растет экспоненциально, оно может делать это только логарифмически много раз, прежде чем превысить некоторое фиксированное значение.