Техпрогон
ВойтиНачать бесплатно
Выбор ответа Middle Скользящее окно спрашивают часто обновлено

Почему вложенный while не даёт O(n²)

Вопрос

В окне переменной длины есть for по r и вложенный while по l. Почему сложность O(n), а не O(n²)?

Попробуйте сами

Выберите вариант, и откроется разбор.

Показать ответ и разбор

Коротко

Правильный ответ: l только растёт и за всё время сдвигается не больше n раз. Каждый указатель монотонно двигается вправо и проходит не больше n позиций.

Варианты ответа

  1. l только растёт и за всё время сдвигается не больше n разправильный ответ
  2. while выполняется максимум один раз на каждой итерации r
  3. JS оптимизирует вложенные циклы и сворачивает их в один
  4. Сложность на самом деле O(n²), O(n) это средний случай

Разбор

Каждый указатель монотонно двигается вправо и проходит не больше n позиций. Суммарно 2n шагов: O(n). Это амортизированный анализ.

  • while может выполниться много раз на одном шаге r, но суммарно ограничен.
  • Движок не меняет асимптотику.
  • O(n²) было бы, если бы l сбрасывался назад.

Ответьте сами, а не прочитайте

В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.

Потренироваться бесплатно

Предыдущий вопрос

Ошибка в обновлении ответа

Следующий вопрос

Скользящее окно

Урок по теме

Паттерн: Скользящее окно

Термины по теме

Скользящее окно

Ещё по теме «Скользящее окно»

Все вопросы модуля