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).
Чи має значення серія?
Так. Кожна друга правильна відповідь поспіль збільшує виплату за наступну, до стелі, тож чистий забіг вартий помітно більше, ніж чотири правильні й дві хибні. Хибна відповідь обнуляє серію.