TwiddleLab / Код / Алгоритмы в движении

O большое: как растут столбики

Урок 5 из 11 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• O большое называет, как число шагов растёт с n: O(1), O(log n), O(n), O(n²).
• Удвой n: O(1) не меняется, O(log n) прибавляет один, O(n) удваивается, O(n²) растёт в 4 раза.
• Константы и мелкие слагаемые отбрасываются: 100n всё ещё O(n), и при большом n оно обгоняет n².

Начать урок

Как идёт урок

1. С 100 пользователями оба приложения работают мгновенно. С миллионом одно всё ещё работает. Какое?

   Начни с программы пар из урока 1.

2. Четыре вида роста. Удваивай n и смотри на столбики.

   График отдаляется, чтобы вместить самый высокий столбик. Дойди до 1024.

3. Теперь гонка в реальном времени.

   Миллион шагов в секунду. Выбери n, нажми «Запуск». Самое большое n попробуй последним.

4. O большое.

   O большое называет рост числа шагов программы при росте n. Оно не смотрит на точные числа и сохраняет форму.

   O(1): одинаковая работа при любом n. O(log n): деление пополам, как в двоичном поиске. O(n): один цикл. O(n²): цикл внутри цикла.

   Константы отбрасываются: 3n + 5 шагов это O(n). При достаточно большом n форма всегда побеждает.

5. Разложи код по росту.

   a это список из n элементов.

6. Твоё приложение неповоротливое: c шагов на каждого пользователя. Конкурент делает n x n.

   Выбери своё c. Потом найди число пользователей, при котором конкурент становится медленнее.

   c x n = n x n ровно при n = c. При любом n больше c n x n больше, и разрыв растёт. Поэтому в O большом константы отбрасывают.

7. Нарисуй y = x² на графике.

   Двигай три точки. Синяя кривая это y = log₂ x.

   Возведение в квадрат: 2 x 2 = 4, 4 x 4 = 16, 6 x 6 = 36. Каждый раз, когда x растёт на 2, y поднимается сильнее, чем в прошлый раз.

8. Программа O(n²) работает 1 секунду на 1000 элементах. Примерно сколько на 10 000?

   Шаги растут как n². (10n)² = 100 n², поэтому время растёт в 100 раз: 1 с превращается в 100 с.

9. Скоростной раунд: выбери гонщика.

   Размер и лимит времени. Нажми на самый медленный класс, который всё ещё успевает. Последний раунд это твоё приложение.

Предыдущий урок: Сортировка вставками · Следующий урок: Сливаем отсортированные стопки · Часть курса: Алгоритмы в движении

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.