Сложность алгоритмов за 5 минут

Что такое сложность алгоритмов и зачем ее считать?

Сложность алгоритма - это мера того, насколько сильно усложняется процесс вычисления при увеличении входных данных.

Пример:

Чтобы пробежаться по всему списку из 10 элементов, нужно сделать 10 итераций. Если список будет из 1000 элементов, то придется выполнить уже в 100 раз больше действий.

А если к тому же каждый третий элемент нужно помещать в новый отдельный список, то придется дополнительно задействовать еще 300+ ячеек памяти.

Зачем считать сложность алгоритма?

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

Что такое О большое?

Начнем с того, что никому не требуется знать точное значение сложности алгоритма. Оценка производится в асимптотических терминах, т.е. отвечаяна вопрос:

Если мы до бесконечности будем увеличивать объем входных данных, как будет меняться работа нашего алгоритма?

Эта асимптотическая оценка обычно производится с помощью О большого или О-нотации. Она показывает, какой функцией ограничена асимптотическая сложность нашего алгоритма. Другими словами, если сложность алгоритма O(g), то с увеличением объема входных данных сложность алгоритма растет не быстрее (или даже чуть медленней) функции g.

Пример:

Сложность перебора коллекции - O(n). Это значит, что сложность алгоритма будет расти линейно. Увеличим объем данныхв 10 раз - сложность вырастет в 10 раз. Увеличим в 100 - вырастет в 100.

Примечание: Также используют и другие нотации: омега, о малое и т.д. Но О большое - основной и наиболее часто встречающийся инструмент.

Основные правила расчёта

1. Если операция не зависит от объема данных, то она имеет константную сложность O(1)

   Примеры:

   • Извлечь первый элемент коллекции
   • Сложить два числа

2. Сложение классов сложности приводит к выбору большей сложности

   • Если нужно сложить 2 числа, а затем умножить результат на 5, то сложность такой операции O(max(1, 1)) = O(1)
   • Если нужно пробежаться в цикле по списку (сложность O(N)), а в конце отобрать только первый элемент (сложность O(1)), то итоговая сложность будет O(max(N, 1)) = O(N)

Примечание: На самом деле происходит не просто выбор максимальной сложности, а их сложение. Например, O(N + 1). Но при стремлении входных данных к бесконечности большая функция (N) задавит меньшую (1). Поэтому и выбирают только максимальную.

3. Сложность IF-блоков рассчитывается по формуле: O(сложность условия) + max(O(код в if), O(код в else)).

   Пример: если число больше N, возвести его в квадрат, иначе проитерировать по списку arr длины N.

   Сложность условия «если число больше N» - O(1), это простое сравнение. Сложность «возвести его в квадрат» - O(1). Сложность «проитерировать по списку arr длины N» - O(N).

   Итоговая сложность: O(1) + max(O(1), O(N)) = O(1) + O(N) = O(N).

4. При умножении классы сложности умножаются

   Пример:

   - Если мы пробегаемся в цикле по коллекции и умножаем каждый элемент на 5, тосложность будет O(N*1), т.к. сложность умножения - O(1) и эту операцию мы повторяем N раз.

   - Если мы пробегаемся в цикле по коллекции и умножаем каждый элемент на все остальные (то есть для каждого элемента пробегаемся еще в одном цикле по остальным элементам), то сложность будет O(N*1)*O(N*1) = O(N*N) = O(N^2).

Основные виды сложности

1. Константная O(1)

   • извлечение первого элемента
   • арифметические операции между числами

2. Линейная O(N)

   • стандартный цикл for

3. Логарифмическая сложность O(logN) - на каждой итерации берется лишь половина элементов

   • алгоритмы типа «Разделяй и Властвуй» (Divide and Conquer), например, бинарный поиск

4. Линеарифметическая или линеаризованная O(n * log n)

5. Логарифмическая сложность O(logN) - на каждой итерации берется лишь половина элементов
   • сортировка слиянием

6. Квадратичная - O(n^2)

   • двойной цикл
   • сортировка пузырьком

Лучшая, худшая и средняя сложность

Не всегда есть возможность полностью оценить сложность алгоритма. Это сильно зависит от входных данных: в одном случае алгоритма может показывать линейную сложность, а в другом - квадратичную.

Пример: в лучшем случае сортировка пузырьком имеет O(N)сложность (когда массив уже отсортирован), в худшем - квадратичную O(N^2).

Поэтому принято оценивать, как минимум, лучший и худший случай. Но ориентироваться лучше на самый плохой вариант:)

В качестве основной характеристики также часто берут «средний» случай. Это сложность алгоритма по усредненным данным. Использовать этот подход удобно, потому что вероятность в точности попасть в «лучший» случай или в «худший» на практике мала.

Пример: Нужно найти заданный элемент в списке из N элементов. В лучшем случае этот элемент будет первым - тогда сложность будет O(1).В худшем - нужный элемент будет последним, тогда сложность будет O(N). Но в среднем придется сделать N/2сравнений, а значит усредненная сложность - O(N/2) = O(N).

Пример расчёта

Давайте посчитаем сложность следующего кода. Функция FindDuplicates проверяет - есть ли в массиве arr дубликаты. Если есть, возвращается True, иначе False.

def FindDuplicates(arr):
     for ind, elem in enumerate(arr):
          if elem in arr[ind+1:]:
               return True
          return False

• Сложность цикла - O(N)
• Сложность создания среза arr[ind+1:] - O(N)
• Сложность проверки in - O(N)
• Сложность операции return - O(1)

Итоговая сложность: O(N)*[O(N) + O(N) + O(1)] = O(N^2)

Получается, что при увеличении входных данных в 2 раза нужно будет выполнить в 4 раза больше операций.