Big-O — назовите сложность кода
Прочитайте фрагмент, назовите его временную сложность и посмотрите кривую роста. Шесть классов, шесть раундов. Бесплатно.
Пять фрагментов, пять из шести классов сложности, каждый по разу.
Как играть
- Прочитайте фрагмент и выберите его временную сложность из шести.
- Кривая роста рисуется после каждого ответа: ваша красным, правильная зелёным.
- Пять классов из шести за забег, без повторов, так что один и тот же ответ верен самое большее один раз.
- Верные ответы подряд приносят больше. Неверный обнуляет серию.
Как это работает
Каждый раунд показывает короткий кусок кода и спрашивает его временную сложность. Вы отвечаете — и рисуется кривая роста, ваша против правильной, так что выбор перестаёт быть ярлыком и становится формой, которую видно. Забег спрашивает пять классов из шести, вперемешку и без повторов, а значит, отвечать всегда одно и то же верно самое большее один раз — и пропущенный класс меняется, так что последний раунд никогда не достаётся методом исключения. Фрагменты подобраны так, чтобы у каждого был один защитимый ответ: без досрочных выходов, без скрытой стоимости библиотечных вызовов и без подсказок о собственной сложности в комментариях. Сортировка везде считается O(n log n) — именно это даёт любая стандартная библиотека. Всё работает на вашем устройстве, никуда ничего не отправляется, регистрироваться негде.
O-нотация описывает, как растёт стоимость, а не какая она. O(n²) с хорошими константами обгоняет раздутый O(n log n) на тех размерах, которые видит большинство настоящего кода, — этому посвящена другая игра на этом сайте.
Частые вопросы
Почему кривая в логарифмическом масштабе?
Потому что иначе шесть классов не помещаются на один график. При n=24 функция константного времени стоит 1, а экспоненциальная — шестнадцать миллионов, так что на линейной оси пять кривых из шести были бы одной плоской линией по низу. Логарифмическая шкала превращает каждый класс в различимый наклон, а его и стоит увидеть.
Сортировка действительно O(n log n)?
Для сортировок сравнением — да: это доказанная нижняя граница и то, что даёт любая стандартная библиотека. Сортировка подсчётом и поразрядная быстрее, потому что не сравнивают, но им нужны предположения о ключах. Когда фрагмент здесь вызывает sort(), это стоит n log n.
Почему нет фрагментов с досрочным выходом?
Потому что досрочный выход превращает худший случай в средний, и тогда ответ перестаёт быть одним классом. Линейный поиск, возвращающийся на первом совпадении, — это O(n) в худшем случае и O(1), если совпадение всегда первое; спрашивать «ту самую» сложность было бы нечестно. Бинарный поиск — исключение: он выходит досрочно и всё равно ровно O(log n).
Серия имеет значение?
Да. Каждый второй верный ответ подряд увеличивает выплату за следующий, до потолка, так что чистый забег стоит заметно больше, чем четыре верных и два неверных. Неверный ответ обнуляет серию.