O(n) - Линейная Сложность

Проблема

Фраза «этот код проходит по массиву» сама по себе ничего не говорит. Один цикл может быть безобидным O(n), а другой - незаметно прятать внутри себя ещё один проход по тем же данным и превращаться в O(n²). На 100 элементах разницы не видно вообще. На 100 000 - один вариант отработает за секунды, а другой будет тормозить часами. Нужно уметь заранее отличать «работа растёт вместе с данными» от «работа растёт быстрее данных» - до того, как программа реально начнёт тормозить у пользователей.

Решение

Алгоритм - это O(n), если он проходит по входным данным один раз: заглядывает в каждый элемент фиксированное число раз (обычно один), не возвращается к уже обработанным частям и не запускает внутри себя ещё один проход по тем же данным. Узнать такой код просто: в нём один цикл, и внутри него нет ещё одного цикла, а сам он идёт от начала до конца массива, строки или списка. Внутри цикла может быть сколько угодно простых действий - сравнение, сложение, запись в переменную - это не важно, потому что их количество не зависит от размера данных n.

Как это работает

У O(n) есть точное определение: существует число c, такое что работы не больше, чем c, умноженное на n, начиная с какого-то размера входа. У linearSearch в худшем случае - ровно n сравнений: не n + 5, не n / 2, а именно n. Здесь c = 1 - это самый чистый пример O(n), какой только бывает.

Пропорциональность хорошо видна на числах. Поиск в массиве из 1 000 элементов в худшем случае - 1 000 сравнений. Поиск в массиве из 1 000 000 элементов - 1 000 000 сравнений: данных стало в 1000 раз больше, и работы стало ровно в 1000 раз больше, не больше и не меньше. Для сравнения: у алгоритма с O(n²) (как Bubble Sort или Insertion Sort из раздела сортировок) тот же рост данных в 1000 раз превращает 1 000 000 операций в 1 000 000 000 000 - в миллион раз больше, а не в тысячу.

Разница с O(n²) видна прямо в коде. У Bubble Sort и Insertion Sort есть цикл внутри цикла: внешний проходит по всем n элементам, а внутри него - ещё один проход, тоже по n элементам. Отсюда n · n = n² сравнений. У linearSearch внутри цикла нет второго цикла - только простые действия вроде сравнения и возврата значения. Поэтому сложность остаётся n · O(1) = O(n), а не n · n.

Самая частая ошибка - спрятанный O(n) внутри другого O(n). Код вида for (const x of arr) { if (arr.includes(x)) { ... } } выглядит как один цикл, но .includes() - это тоже проход по всему массиву, и он запускается на каждой итерации внешнего цикла. На массиве из 10 000 элементов это уже не 10 000 операций, а до 100 000 000. Код остаётся O(n²) - просто вторая n спряталась внутри готового метода вместо явного for.

Когда об алгоритме говорят просто «O(n)» без уточнений, почти всегда имеют в виду худший случай. У linearSearch лучший случай - O(1) (нужный элемент оказался первым), средний случай на случайных данных - примерно n / 2 сравнений, а худший случай - все n сравнений (элемента нет вообще, или он последний). Разница между этими тремя случаями - отдельная тема, ей посвящён материал «Лучший/средний/худший случай».

На однопроходных O(n)-алгоритмах держится обработка больших объёмов данных: подсчёт строк в лог-файле, вычисление контрольной суммы файла, поиск через grep. Все они читают вход ровно один раз, без повторных проходов и без загрузки всего файла в память сразу - именно за счёт линейности они справляются с файлами в десятки гигабайт.

O(n) - это своего рода нижняя граница для любой задачи, где нужно хотя бы посмотреть на каждый элемент входа: быстрее, чем прочитать все n элементов, задачу решить не получится. Поэтому если данные не отсортированы и заранее не подготовлен индекс, поиск, сумма или максимум не могут быть быстрее O(n). А если код уже уместился в один проход без вложенности - он уже достиг этой границы.

Нюансы выбора

Задачи, где нужно увидеть все данные целиком - сумма, среднее, максимум, минимум, подсчёт вхождений. Результат просто нельзя получить, не посмотрев на каждый элемент хотя бы раз.

Разовый поиск в неотсортированных данных - если массив не отсортирован и больше не понадобится, строить дерево или хеш-таблицу ради одного поиска дороже, чем просто пройти по массиву.

Против O(log n) - если данные уже отсортированы или под рукой есть хеш-таблица, O(n) почти всегда стоит заменить на бинарный поиск или прямой доступ по ключу. Здесь линейность - уже не предел возможностей, а упущенная возможность ускориться.

Как кирпичик, а не как цель - простые однопроходные операции (map, filter, sum) свободно комбинируются друг с другом и остаются в сумме O(n) - если, конечно, не вкладывать их одну в другую по тем же данным.

Примеры в коде

Утилиты Unix wc, grep, cat - все они читают файл за один проход, поэтому спокойно работают с файлами, которые целиком не помещаются в оперативную память.

Обработка потоков событий (Kafka, лог-агрегаторы) - каждое событие обрабатывается один раз, сразу при поступлении, без возврата к предыдущим. Линейность здесь заложена прямо в архитектуру.

Контрольные суммы и хеш-функции (MD5, SHA-256) - считаются за один проход по байтам файла, поэтому время расчёта растёт линейно вместе с размером файла.

Bubble Sort и Insertion Sort (в разделе сортировок) - наглядный пример противоположной ситуации: их внутренний цикл превращает один внешний O(n)-проход во вложенный O(n²). Хороший пример того, чем O(n) точно не является.

Когда применять

• Когда данные нужно обработать целиком хотя бы раз: посчитать сумму, найти максимум, скопировать элементы. Такие задачи сами требуют «тронуть» каждый элемент минимум один раз.
• Когда данные не отсортированы и строить отдельную структуру (дерево, индекс) ради одного разового поиска не имеет смысла - один проход обойдётся дешевле подготовки.

Примеры из практики

• Array.prototype.map/filter/forEach в JavaScript и списковые включения в Python - под капотом это один проход по всем элементам, O(n) по самому устройству метода.
• grep читает файл построчно, ровно один раз - классический пример O(n) относительно размера файла, без предварительного построения индекса.