Что охватывал курс и что пропустил
Курс Хэмминга охватывал: аналого-цифровое преобразование, исправление ошибок, моделирование, статистику, численный анализ и 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) — Линеарифмическая. Почти линейная, но чуть хуже. Примеры: сортировка слиянием, эффективные алгоритмы поиска кратчайшего пути (Дейкстра с кучей). При N=10 000: ~133 000 операций.
O(N²) — Квадратичная. Стоимость растёт взрывным образом. Примеры: вызов list.contains() внутри цикла по тому же списку, сортировка пузырьком, наивное сравнение всех пар. При 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
ratio: 10x
N=1,000 сравнений:
O(N): 1,000
O(N²): 1,000,000
ratio: 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) проверка принадлежности
for node in graph:
if node not in visited: # O(1) хеш-поиск
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». Он ввёл Ω (Омега) для нижних оценок и Θ (Тета) для точных оценок, завершив трёхсимвольный словарь, которым пользуется информатика сегодня. Он также выступил за стандартизацию использования этих символов в области — акт осознанной стандартизации, ускоривший их распространение.
К началу 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+ open-source проектахИнструмент Бахманна провёл 74 года в чистой математике — видимый каждому математику, но невидимый каждому программисту. Кнут увидел возможность его переноса. Хэмминг — работая в ту же эпоху и сотрудничая с тем же сообществом вычислителей — так и не включил его в свой курс.
Почему стандартизация Кнута имела значение
Статья Кнута 1976 года сделала больше, чем просто ввела Ω и Θ. В ней утверждалось, что области нужна единообразная нотация, а её отсутствие реально вредит. В разных учебниках O использовали по-разному — иногда как верхнюю границу, иногда как приближение, иногда без указания, важны ли константы. Кнут навёл порядок.
Это динамика «именования паттернов» Хэмминга, применённая к самой нотации. До стандартизации Кнута инженеры не могли точно передавать утверждения о сложности между учебниками, статьями или командами. После стандартизации фраза «работает за O(N log N)» имела ровно одно значение независимо от того, кто её произнёс.
Кнут также дал неформальную интерпретацию: «O(f(n)) означает, что время работы не превышает константу, умноженную на f(n), для всех достаточно больших n». Эта интерпретация — верхняя граница с точностью до константы для больших входных данных — стала стандартной интуицией, которую усваивает каждый программист.