Алгоритмическая сложность в программировании
Ранее я писал что зарабатываю разработкой программного обеспечения, и в этот раз я хотел бы рассказать о понятии алгоритмической сложности.
Обычно нет разницы, насколько сложным будет алгоритм, если вам нужно обрабатывать небольшие данные, или если задача разовая. Если же данных много или предполагается их рост, программисту приходится задумываться об эффективности написанного им кода. И обычно сложность алгоритма является второй самой главной его характеристикой (первая - функциональная корректность).
Для начала на нескольких примерах поясню, какие могут быть зависимости между входными и выходными данными.
Пример 1. В меню ресторана множество блюд, но мы не смотрим меню, а берем как всегда макарошки с котлеткой. Здесь входные данные - меню, результат обработки - заказ. Если завтра меню увеличится, для нас время заказа (сложность) не изменится.
Пример 2. В компании есть задачи для разработчиков, и для каждой задачи требуется три программиста. Чем больше задач, тем больше требуется программстов.
Пример 3. Люди по одному заходят в комнату и здороваются за руку с находящимися там людьми. Первому пришедшему здороваться не с кем, второй поздоровается с первым, третий с ними двумя, и тд. Видно, что с ростом количества людей (входные данные) совокупное количество рукопожатий (сложность) растет еще быстрее.
Можно также сравнивать разные типы зависимостей для упрощения расчетов. Например, в день получки я покупаю бутылку шампанского за 1000р, чтобы отметить это дело. Также с зарплаты приходится платить подоходный налог (13%). Стоимость бутылки шампанского не меняется, а вот с ростом зарплаты абсолютное значение налога растет. При достаточно высокой зарплате можно сказать, что все затраты идут на налог, а тратами на шампанское можно пренебречь.
Теперь, когда примеров достаточно, можно попробовать ввести формальные обозначения, не перегружая все же текст понятиями из математики. Обозначим количество данных на входе как n, а сложность алгоритма как О ("о большое"). Сложность алгоритма указывается скобках в виде функции от n. Тут же посчитаем сложность алгоритмов для примеров выше:
Пример 1. Количество блюд в меню обозначим за n. Сложность не зависит от количества блюд в меню, требуется фиксированное время на заказ, обозначается это так: O(n) = const. Константа может быть разная для разных людей (кто-то всегда дополнительно заказывает компот, на это нужно время), но все равно не зависит от количества блюд в меню. Для удобства сравнения константу выкидывают, и пишут просто: O(n) = 1. Такая сложность называется константной.
Пример 2. Количество задач обозначим за n, тогда для разработки требуется 3*n программистов. Сложность O(3*n) без учета умножения на константу можно записать как О(n) - такая сложность называется линейной.
Пример 3. Количество рукопожатий можно вычислить по формуле суммы алгебраической прогрессии: n * (n-1) / 2. При больших значениях n можно пренебречь единицей в числителе, и без учета умножения на константу получаем оценку сложности - О(n^2). Это квадратичная сложность.
Еще раз повторю, что оценка имеет смысл только на достаточно больших входных данных. Например, график параболы может лежать ниже графика линейной функции при небольших значениях аргумента - это не наш случай. Любители математики могут также подумать, почему у графика логарифмической зависимости не требуется указывать основание логарифма.
Приведу также несколько примеров типовых алгоритмов в порядке возрастания их сложности:
- O(1) - поиск в хеш таблице
- O(log n) - поиск в отсортированном массиве, в дереве поиска
- O(n) - поиск в не отсортированном массиве, сортировка подсчетом
- O(n * log n) - большинство алгоритмов сортировки
- O(n^2) - сортировка пузырьком, худший случай сортировки бинарным деревом
С понятием сложности разработчику приходится сталкиваться каждый день, в основном на простых случаях. Например, разработчик может решить добавить индекс, чтобы снизить сложность поиска по базе данных от линейной (полный перебор) до логарифмической или константной.
Вопросы на сложность алгоритмов очень любят задавать на собеседованиях на позицию junior разработчиков. У начинающих разработчиков нет практических знаний, поэтому вопросы касаются в основном теории. Если дают задачу на алгоритмы, то ожидают что соискатель предоставит решение с минимальной сложностью. Если вы начинающий разработчик, то будет полезно ознакомиться с типовыми алгоритмами, чтобы понимать как можно использовать их для решения прикладных задач.