Выбор ответа Junior Сложность спрашивают часто обновлено
Цикл с делением пополам
Вопрос
Сколько итераций сделает цикл в зависимости от n?
let steps = 0;
while (n > 1) {
n = Math.floor(n / 2);
steps++;
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(log n). На каждом шаге n уменьшается вдвое, значит шагов примерно log₂ n: O(log n). - O(n): так было бы при n--. - O(n / 2): константа не меняет класс, это O(n), и деление идёт не на константу шагов. - O(√n): так растёт цикл for (i = 1; i i <= n;…
Варианты ответа
- O(n)
- O(n / 2)
- O(√n)
- O(log n)правильный ответ
Разбор
На каждом шаге n уменьшается вдвое, значит шагов примерно log₂ n: O(log n).
- O(n): так было бы при
n--. - O(n / 2): константа не меняет класс, это O(n), и деление идёт не на константу шагов.
- O(√n): так растёт цикл
for (i = 1; i * i <= n; i++).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.