Примеры временной и пространственной сложности

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

На графике представлены некоторые виды функций, которые описывают такую зависимость:

Чтобы понять разницу в работе алгоритмов с разной оценкой сложности О(n), разберём пример.

Допустим, вы работаете со старым медленным компьютером, выполняющим 1000000 операций в секунду. Вычислительная сложность вашего алгоритма O(n). На входе 1000 элементов. Чтобы произвести необходимые вычисления, нужна всего 0,001 секунды. Если на вход поступит 10000 элементов, потребуется 0,01 секунда, для работы алгоритма на 1000000 элементов — 1 секунда. Намного больше, чем для 1000 элементов. Но вроде бы нестрашно.

Теперь представьте, что сложность алгоритма O(n²). Для обработки 1000 элементов нужно около 1000000 операций, и на это будет потрачена 1 секунда. Для 10000 элементов нужно почти 2 минуты, а для 1000000 — почти 10 дней. Разница уже существенная.

Видите, как может вырасти время исполнения алгоритма при увеличении объёма входных данных. В реальности компьютеры работают намного быстрее. Современные процессоры совершают не миллионы, а миллиарды операций в секунду.

Современные приложения обрабатывают громадные массивы данных. Представьте, что у вас онлайн-магазин с миллионами пользователей. Записи в базе данных у него копились несколько лет. Посетитель отправляет запрос на сайт и ожидает получить ответ сразу. Есть разные способы уменьшить время ожидания. Например, купить сервер помощнее, или поставить больше серверов и отправлять разные запросы на разные машины, выбрать более быстрые сетевые соединения или различные типы баз данных, скажем, key-value хранилища, способные быстро отвечать на запрос. Но один из главных приёмов — выбор эффективных алгоритмов обработки данных.