Почему объём данных меняет время работы
О-нотация описывает, как растёт число операций алгоритма, когда увеличивается входной набор данных. Буква n обычно обозначает количество записей: например, число товаров в каталоге или сообщений в чате. Это не секундомер и не прогноз точного времени — это способ сравнить, как алгоритмы ведут себя при масштабировании.
Если алгоритм проходит по каждой записи один раз, его работа растёт примерно пропорционально n: вдвое больше данных — примерно вдвое больше проверок. Если же для каждой записи он снова перебирает весь набор, операций становится порядка n². Тогда удвоение данных может увеличить их число примерно вчетверо. Такой перебор легко незаметен на маленьком тестовом списке, но ощутим на реальном объёме.
Откуда берётся замедление
Представим поиск совпадений: программа берёт очередного пользователя и сравнивает его со всеми остальными. При сотне пользователей это ещё может казаться мгновенным. Когда пользователей становится гораздо больше, алгоритм выполняет уже не просто больше сравнений — каждый новый участник добавляет работу сразу для множества пар.
Поэтому разработчики проверяют не только то, правильно ли работает код, но и то, сколько действий ему потребуется при росте входных данных. Иногда помогает другой способ организации данных — например, структура, позволяющая быстро находить запись, а не просматривать список целиком.
Что О-нотация не говорит
Классы роста не учитывают все детали конкретного устройства, реализации и самих данных. Алгоритм с более быстрым ростом может проигрывать на небольших наборах из-за дополнительных накладных расходов. Но по мере увеличения объёма решающим часто становится не число строк в программе, а то, как устроены повторяющиеся проходы по данным. Именно поэтому удачный тест на десятке записей ещё не гарантирует, что тот же код останется быстрым для реальных пользователей.
