Що охоплював курс і що пропустив
Курс Геммінга охоплював: аналого-цифрове перетворення, виправлення помилок, моделювання, статистику, чисельний аналіз та n-вимірну геометрію. Він мислив обчислювально — обробка сигналів, теорія кодування, цифрове фільтрування потребують обчислювального мислення.
Він ніколи не викладав систематично алгоритмічну складність.
Чому існував цей розрив
Ментальна модель Геммінґа сформувалася в епоху, коли апаратні обмеження домінували. Питання звучало так: скільки транзисторів на чипі? Алгоритм запускався на доступному обладнанні. При N=100 алгоритм O(N²) коштує 10 000 операцій. При N=1 000 — 1 000 000. При N=10 000 (звичайна величина сьогодні в графах залежностей, соціальних мережах і менеджерах пакетів): 100 000 000. Різниця між O(N) та O(N²) була непомітною в масштабах, з якими працював Геммінґ, і катастрофічною в масштабах, які населяли його студенти.
Дональд Кнут опублікував The Art of Computer Programming починаючи з 1968 року — того ж року, коли Геммінґ перебував на піку дослідницької продуктивності. Нотація Big O стала стандартним алгоритмічним словником у 1970-х і 1980-х. Курс Геммінґа датується 1995 роком, але його ментальна модель обчислень сформувалася раніше. Він ніколи не оновлював цей розділ.
Фундаментальне за власним тестом Геммінґа
Тест Геммінґа на фундаментальне: (1) воно проіснувало довгий час, (2) решту галузі можна вивести з нього стандартними методами.
Big O проходить обидва тести. Аналіз швидкості зростання існує з часів Кнута. З нього виводять вибір алгоритму, вибір структури даних і прогнозування продуктивності — більшість практичної інформатики випливає з питання «як зростає вартість зі зростанням N?». Геммінґ пропустив найстійкіше фундаментальне своєї власної галузі.
Big O як фундаментальне
Геммінґ вчив, що фундаментальні речі переживають конкретні технології. Він наводив приклад з обчислювальним аналізом: винайдений одного разу, він застосовується в фізиці, інженерії, економіці та біології століттями. Периферійні інструменти приходять і йдуть; фундаментальні — накопичуються.
Як зростає вартість
Big O вимірює, як зростає вартість зі зростанням вхідних даних. Не постійний коефіцієнт — темп. Два алгоритми, які обидва виконуються «за кілька мілісекунд» при N=100, можуть розійтися у 10 000 разів при N=10 000, якщо один працює за O(N), а інший — за O(N²).
Основні класи складності
O(1) — Константа. Вартість однакова незалежно від N. Приклади: пошук у хеш-таблиці за ключем, доступ до елемента масиву за індексом, push/pop стеку. Подвоєння N нічого не змінює.
O(log N) — Логарифмічна. Кожен крок зменшує обсяг роботи вдвічі. Приклади: бінарний пошук у відсортованому масиві, BVH-запит у просторі ігрового рушія, операції зі збалансованим двійковим деревом. При N=1 000 000: log₂(1 000 000) ≈ 20 кроків.
O(N) — Лінійна. Вартість зростає пропорційно до вхідних даних. Приклади: лінійний обхід списку, читання файлу, підрахунок елементів у колекції. При N=10 000: 10 000 операцій.
O(N log N) — Лінійно-логарифмічна. Майже лінійна, але трохи гірша. Приклади: merge sort, ефективні алгоритми пошуку найкоротшого шляху (Дейкстра з купою). При N=10 000: ~133 000 операцій.
O(N²) — Квадратична. Вартість зростає вибухово. Приклади: list.contains() всередині циклу по тому ж списку, bubble sort, наївне порівняння всіх пар. При N=1 000: 1 000 000 операцій. При N=10 000: 100 000 000 операцій.
O(2^N) — Експоненціальна. Непридатна за будь-якого значущого масштабу. Приклади: перебір усіх комбінацій, пошук усіх підмножин. При N=30: понад 1 000 000 000 операцій.
Масштаб, на якому це стає помітно
Порівнянь при N=10:
O(N): 10
O(N²): 100
співвідношення: 10x
N=1 000 порівнянь:
O(N): 1 000
O(N²): 1 000 000
співвідношення: 1 000x
N=10 000 порівнянь:
O(N): 10,000
O(N²): 100,000,000
ratio: 10,000xПри N=10 різниця майже непомітна. При N=10 000 алгоритм O(N²) працює в 10 000 разів повільніше. Саме тому MOAD-0001 залишався непомітним десятиліттями: графи, на яких він запускався в 1993 році, мали 50 вузлів. До 2020 року той самий код працював на графах залежностей із 50 000 вузлів.
Класифікуйте три операції
Застосуйте класи складності до конкретних операцій. Ключове питання для кожної: скільки операцій потрібно при зростанні N?
Правильний код, неправильна крива зростання
Правильний код, що працює за O(N²), дає ті самі результати, що й код за O(N). Тести проходять. Вивід збігається. Винятків не виникає. Дефект прихований у кривій зростання.
Ця властивість робить дефекти O(N²) осадовими: вони застигають усередині робочого коду і стають помітними лише тоді, коли N перевищує певний поріг. Код не змінився. Змінився світ навколо нього.
MOAD-0001: Осадовий дефект
Найпоширеніший приклад: visited = [] всередині циклу обходу графа.
visited = []
for node in graph:
if node not in visited: # O(N) сканування при кожному виклику
visited.append(node)
process(node)Кожен виклик not in visited сканує від 0 до len(visited)-1 елементів. N викликів × N/2 середніх сканованих елементів = O(N²) загалом. Виправлення: один рядок.
visited = set() # O(1) membership test
for node in graph:
if node not in visited: # O(1) hash lookup
visited.add(node)
process(node)Та сама поведінка. Той самий результат. Ті самі тести проходять. Швидкість зростання змінюється з O(N²) на O(N). При N=1,000: у 1,000 разів швидше. При N=10,000: у 10,000 разів швидше.
Чому епоха Геммінга заклала основу для цього
У ранніх Java та C ArrayList (динамічний масив) був стандартним послідовним контейнером. Множини існували, але не були ідіоматичними — розробники зверталися до того, що було звичним. Обхід графа 1993 року при N=50 виконувався за мікросекунди з visited = []. Цей код потрапив у систему контролю версій, його копіювали, обгортали в бібліотеки, поширювали через менеджер пакетів. До 2020 року той самий шаблон працював на графах залежностей із 50,000 вузлів.
Код був правильним у 1993 році. Він став дорогим, коли навколишній світ змінився. Епоха Геммінга заклала основу для цього класу дефектів, ніколи не ставлячи питання про швидкість зростання.
Діагностика та виправлення
Застосуйте діагностику: знайдіть шаблон O(N²), визначте виправлення.
Які зміни в іменуванні
До того, як Big O отримав назву, програмісти помічали: «це працює повільно». Вони профілювали. Вони переписували. Але вони не могли навчити шаблону — могли лише вказувати на окремі випадки. Шаблон без назви не може поширюватися.
Після того, як Big O отримав назву, старший інженер міг сказати «це O(N²), замініть на множину», і молодший інженер міг зрозуміти, застосувати та в свою чергу навчити цьому шаблону. Назва зробила шаблон переносною одиницею знань.
Геммінг знав цю динаміку в інших галузях. Він описав, як назва «спагеті-код» у 1960-х дозволила спільноті розпізнавати, обговорювати та зрештою викорінити клас дефектів, з яким усі стикалися, але який ніхто не назвав. Той самий механізм стосується класів складності.
Unhamming додає словник, який Геммінг пропустив: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Ці назви дозволяють бачити криву зростання в коді, який ви читаєте, передбачати продуктивність на масштабі та точно повідомляти про виправлення. Вони задовольняють власний критерій Геммінга для фундаментального: довговічність і здатність породжувати решту галузі. [TITLE who_coined_big_o/]
Від теорії чисел до комп'ютерних наук
Позначення Big O не походить із комп'ютерних наук. Воно виникло в чистій математиці — зокрема в теорії чисел — за 74 роки до того, як Дональд Кнут адаптував його для алгоритмів.
Пауль Бахманн, 1894
Пауль Бахманн, німецький математик, увів позначення O у своїй книзі 1894 року Die Analytische Zahlentheorie (Аналітична теорія чисел). Йому потрібен був компактний спосіб виразити, що одна величина зростає не швидше за іншу, з точністю до сталої. Запис «f(n) = O(g(n))» означав: f зростає не швидше за g. Це дозволило математикам-теоретикам чисел міркувати про похибки в наближеннях, не відстежуючи точні сталі.
Бахманн не думав про цикли, структури даних чи час виконання. Він думав про розподіл простих чисел — зокрема про похибки в теоремі про розподіл простих чисел.
Едмунд Ландау, 1909
Едмунд Ландау, інший німецький математик, популяризував це позначення у своїй праці 1909 року Handbuch der Lehre von der Verteilung der Primzahlen (Довідник з теорії розподілу простих чисел). Ландау також увів споріднене позначення o (little-o) і настільки широко використовував усе сімейство асимптотичних символів, що це сімейство стали називати нотацією Бахманна–Ландау або просто нотацією Ландау.
Протягом шести десятиліть позначення O існувало виключно в математиці. Жоден програміст не думав про нього.
Дональд Кнут, 1968 & 1976
Дональд Кнут переніс це позначення в комп'ютерні науки. У книзі The Art of Computer Programming (Том 1, 1968) Кнут використав нотацію O для опису часу виконання алгоритмів — пряме перенесення інструменту Бахманна в нову галузь. Він першим почав систематично застосовувати її для аналізу алгоритмів.
У 1976 році Кнут опублікував коротку статтю в SIGACT News під назвою «Big Omicron and Big Omega and Big Theta». Він увів Omega (Ω) для нижніх меж і Theta (Θ) для точних меж, завершивши трисимвольний словник, яким сьогодні користується комп'ютерна наука. Він також виступав за стандартизацію використання цих символів у галузі — свідомий крок стандартизації, який прискорив їхнє поширення.
На початку 1980-х років Big O з’явився в усіх підручниках з алгоритмів. До 1990-х років це стало стандартною лексикою співбесід.
Шлях завдовжки 74 роки
1894 — Бахманн вводить O в теорії чисел
1909 — Ландау популяризує O, o та всю родину позначень
1953 — Гаммінг розпочинає дослідження в Bell Labs (так і не знайомиться з Big O як інструментом CS)
1968 — Кнут застосовує O для аналізу алгоритмів у TAOCP, том 1
1976 — Кнут додає Omega та Theta; виступає за стандартизацію
1980-ті — Big O входить до всіх навчальних програм CS
1993 — Утворюється шар осаду MOAD-0001 у продакшн-коді
1995 — Гаммінг викладає останню версію свого курсу; так і не охоплює Big O
2026 — MOAD-0001 виявлено в 1 000+ проєктах з відкритим кодомІнструмент Бахмана провів 74 роки в чистій математиці — його бачили всі математики, але жоден програміст. Кнут побачив можливість пересадити його. Геммінг — працюючи в ту саму епоху та співпрацюючи з тією ж обчислювальною спільнотою — так і не зробив його частиною свого курсу.
Чому стандартизація Кнута мала значення
Стаття Кнута 1976 року зробила більше, ніж просто ввела Omega та Theta. Вона доводила, що галузі потрібна узгоджена нотація, а неузгоджена нотація завдає реальної шкоди. Різні підручники використовували O для позначення різних понять — іноді верхньої межі, іноді наближення, іноді без уточнення, чи важливі константи. Кнут усе це впорядкував.
Це приклад динаміки найменування патернів Геммінга, застосованої до самої нотації. До того, як Кнут стандартизував символи, інженери не могли точно передавати твердження про складність між підручниками, статтями чи командами. Після стандартизації фраза «працює за O(N log N)» мала лише одне значення, незалежно від того, хто її вимовляв.
Кнут також запропонував неформальне тлумачення: «O(f(n)) означає, що час виконання не перевищує константи, помноженої на f(n), для всіх достатньо великих n». Це тлумачення — верхня межа з урахуванням константи для великих вхідних даних — стало стандартною інтуїцією, яку вивчає кожен програміст.