Сложность алгоритмов и операций на примере Python

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

Такой тип анализа называется статическим, так как не требует запуска программы, – в противовес динамическому, или эмпирическому, анализу, при котором проводятся измерения параметров работающего кода.

Классы сложности операций в Python

Самое базовое понятие статического анализа – O(1). Этот класс сложности имеют операции, которые выполняются за константное время, например, создание переменной или сложение небольших чисел.

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

Параметр N, который вы встретите далее, – это размер структуры данных – len(data_structure).

Рассмотрим основные операции некоторых структур данных в Python.

Списки (lists)

Кортежи (tuples) поддерживают все операции, которые не изменяют структуру данных – и они имеют такие же классы сложности, как у списков.

Множества (sets)

Ряд операций со множествами имеет сложность O(1), в отличие от аналогичных операций со списками и кортежами. Более быстрая реализация обусловлена тем, что множествам не требуется хранить информацию о порядке элементов.

Неизменяемые множества (frozen sets) поддерживают все операции, которые не изменяют структуру данных – и они имеют такие же классы сложности, как у обычных множеств.

Словари (dict и defaultdict)

Как видно, большинство операций со словарями имеют сложность O(1).

Тип defaultdict поддерживает все эти операции с теми же классами сложности. Таким образом, вызов конструктора в том случае, если значения не найдены в defaultdict, имеет сложность O(1).

Тонкости анализа

Обратите внимание, что операция for i in range(...) имеет сложность O(len(...)). Для for i in range(1, 10) она равна O(1).

Если len(alist) – это N, тогда for i in range(len(alist)) будет иметь сложность O(N), так как цикл выполняется N раз.

При этом for i in range(len(alist)/2) также имеет сложность O(N). В этом случае цикл выполняется N/2 раз, и мы можем отбросить константу 1/2. При увеличении размера списка вдвое выполняемая работа также удваивается.

Точно так же for i in range(len(alist)/1000000) имеет сложность O(N). Это важно понять, так как нас интересует, что происходит, когда N стремится к бесконечности.

***

При сравнении двух списков на равенство, класс сложности должен быть O(N), как указано в таблице выше. Однако в реальности это значение нужно умножить на O==(...), где O==(...) это класс сложности для операции сравнения (==) двух значений в списке. Если мы работаем с целыми числами (int), то сложность сравнения будет равна O(1), если со строками (string), то в худшем случае мы получим O(len(string)).

Эта проблема возникает при любом сравнении, однако мы в дальнейших расчетах будем предполагать, что эта операция имеет сложность O(1) – например, для чисел и строк малой/фиксированной длины.

Составные классы сложности

Разобравшись со сложностью отдельных операций мы переходим к их комбинированию.

Закон сложения для O-нотации

$$O(f(n))+O(g(n))=O(f(n)+g(n))$$

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

Таким образом,

$$O(N)+O(\log ?N)=O(N+\log ?N)=O(N)$$

так какN растет быстрее, чем log N:

$$\underset{x?\mathrm{?}}{lim}\frac{\log ?N}{N}=0$$

Это правило позволяет вычислить класс сложности для последовательности операций. Например, сначала мы выполняем выражение со сложностью O(f(n)), а следом за ним – O(g(n)). Тогда выполнение обоих выражений (одно за другим) будет иметь сложность O(f(n)) + O(g(n)), то есть O(f(n) + g(n)).

Пример

Вызов функции f(...) имеет сложность O(N), а вызов g(...) – O (N * log N). Вызываем эти функции друг за другом:

         f(...) g(...)     

Сложность этого действия будет равна:

$$O(N)+O(N\log ?N)=O(N+N\log ?N)=O(N\log ?N)$$

Если мы вызовем функцию f(...) дважды:

         f(...) f(...)     

то получим:

$$O(N)+O(N)=O(N+N)=O(2N)=O(N)$$

Константа 2 в вычислениях отбрасывается.

Условия

Отдельно разберем исполнение условий (if). Сначала выполняется само условие, а затем один из блоков (if или else).

         if test:   block 1 else:   block 2     

Предположим, что вычисление условия test имеет сложность O(T), блока block 1 – O(B1), а блока block 2 – O(B2).

Тогда сложность всего кода будет равна:

$$O(T)+max(O(B1),O(B2))$$

test выполняется всегда, а один из блоков следом за ним – то есть последовательно. В худшем случае будет выполнен блок с наивысшей сложностью.

Подставим реальные значения:

• test – O(N),
• block 1 – O(N²),
• block 2 – O(N).

и вычислим сложность кода:

$$O(N)+max(O(N^2),O(N))=$$

$$O(N)+O(N^2)=O(N+N^2)=O(N^2)$$

Если бы операция test имела класс сложности O(N³), то общая сложность кода составила бы O(N³).

$$O(N^3)+max(O(N^2),O(N))=$$

$$O(N^3)+O(N^2)=O(N^3+N^2)=O(N^3)$$

Фактически, общий класс сложности для if-условий можно записать еще проще:

$$O(T)+O(B1)+O(B2)$$

Для первого примера в этом случае получим:

$$O(N)+O(N^2)+O(N)=O(N^2)$$

В O-нотации мы всегда отбрасываем менее значимые элементы – по сути это аналогично работе функции max. Запись с max лучше отражает суть вычисления, но вы можете выбрать любой удобный для вас вариант.

Закон умножения для O-нотации

$$O(f(n))?O(g(n))=O(f(n)?g(n))$$

Если мы повторяем O(N) раз некоторый процесс с классом сложности O(f(N)), то результирующий класс сложности будет равен:

$$O(N)?O(f(N))=O(N?f(N))$$

Предположим, некоторая функция f(...) имеет класс сложности O(N²). Выполним ее в цикле N раз:

         for i in range(N):     f(...)     

Сложность этого кода будет равна:

$$O(N)?O(N^2)=O(N?N^2)=O(N^3)$$

Это правило позволяет вычислять класс сложности для выполнения некоторого повторяющегося несколько раз выражения. Необходимо умножить класс сложности количества повторений на класс сложности самого выражения.

Статический анализ на практике

Возьмем три разные функции, которые решают одну и ту же задачу – определяют, состоит ли список из уникальных значений (не имеет дубликатов). Для каждой функции вычислим класс сложности.

Для всех трех примеров размер списка обозначим как N, а сложность операции сравнения элементов примем за O(1).

Алгоритм 1

Список уникален, если каждое его значение не встречается ни в одном последующем индексе. Для значения alist[i] последующим фрагментом списка будет срез alist[i+1:].

         def is_unique1 (alist : [int]) -> bool:   for i in range(len(alist)):             # 1     if alist[i] in alist[i+1:]:           # 2       return False                        # 3   return True                             # 4     

Определим сложность для каждой строки метода:

1. O(N) – для каждого индекса. Создание объекта range требует выполнения трех последовательных операций: вычисления аргументов, передачу их в __init__ и выполнение тела __init__. Две последние имеют класс сложности O(1). Сложность len(alist) также O(1), поэтому общая сложность выражения range(len(alist)) – O(1) + O(1) + O(1) = O(1).
2. O(N) – получение индекса + сложение + создание среза + проверка in: O(1) + O(1) + O(N) + O(N) = O(N)
3. O(1) – в худшем случае никогда не выполняется, можно проигнорировать.
4. O(1) – в худшем случае всегда выполняется.

Таким образом, класс сложности целой функции is_unique1 равен:

$$O(N)?O(N)+O(1)=O(N^2)$$

Если размер списка увеличится вдвое, то выполнение функции займет в 4 раза больше времени.

***

Возможно, вы хотели написать так:

$$O(N)?(O(N)+O(1))+O(1)$$

ведь выражение if cостоит из вычисления самого условия (O(N)) и блока return False (O(1)). Но в худшем случае этот блок никогда не будет выполнен и цикл продолжится, поэтому мы не включаем его в формулу. Но даже если добавить его, то ничего не изменится, так как O(N) + O(1) – это по-прежнему O(N).

Кроме того, в худшем случае вычисляемый срез списка – это alist[1:]. Его сложность – O(N-1) = O(N). Однако, когда i == len(alist) этот срез будет пуст. Средний срез содержит N/2 значений, что по-прежнему даем нам сложность O(N).

***

Вместо срезов можно использовать вложенный цикл. Сложность функции при этом не изменится.

         def is_unique1 (alist : [int]) ->bool:   for i in range(len(alist)):          # O(N)     for j in range(i+1, len(alist)):   # O(N)       if alist[i] == alist[j]          # O(1)         return False                   # O(1)  return True                           # O(1)     

Класс сложности целой функции тот же:

$$O(N)?O(N)?O(1)+O(1)=O(N^2)$$

Алгоритм 2

Список уникален, если после его сортировки рядом не находятся одинаковые значения.

Сначала мы копируем список, чтобы не изменять исходную структуру сортировкой – функции обычно не должны влиять на входящие параметры.

         def is_unique2 (alist : [int]) -> bool:   copy = list(alist)             # 1   copy.sort()                    # 2   for i in range(len(alist)-1):  # 3     if copy[i] == copy[i+1]:     # 4       return False               # 5   return True                    # 6     

Сложность по строчкам:

1. O(N).
2. O(N log N) – для быстрой сортировки.
3. O(N) – на самом деле N-1, но это то же самое. Операции получения размера списка и вычитания имеют сложность O(1).
4. O(1) – сложение, две операции получения элемента по индексу и сравнение – все со сложностью O(1).
5. O(1) – в худшем случае никогда не выполняется.
6. O(1) – в худшем случае всегда выполняется.

Общий класс сложности функции is_unique2:

$$O(N)+O(N?\log ?N)+O(N)?O(1)+O(1)=$$

$$O(N+N\log ?N+O(N?1)+1)=$$

$$O(N+N\log ?N+N+1)=O(N\log ?N+2N+1)=O(N\log ?N)$$

Сложность этой реализации меньше, чем is_unique1. Для больших значений N is_unique2 будет выполняться значительно быстрее.

Наибольшую сложность имеет операция сортировки – она занимает больше всего времени. При удвоении размера списка именно сортировка займет больше половины добавившегося времени выполнения.

Класс сложности O(N log N) хуже, чем O(N), но уже значительно лучше, чем O(N²).

Фактически, в код метода можно внести одно упрощение:

         # было copy = list(alist)    # O(N) copy.sort()           # O(N log N)  # стало copy = sorted(alist)  # O(N log N)     

Функция sorted создает список с теми же значениями и возвращает его отсортированную версию. Поэтому нам не требуется явно создавать копию.

Это изменение ускорит выполнение кода, но не повлияет на его сложность, так как O(N + N log N) = O(N log N). Ускорение – это всегда хорошо, но намного важнее найти алгоритм с минимальной сложностью.

Нужно отметить, что is_unique2 работает только в том случае, если все значения в списке сравнимы между собой (для сортировки используется оператор сравнения <). Если список заполнен одновременно строками и числами, ничего не получится. В то же время is_unique1 использует только оператор ==, который может сравнивать значения разных типов без выбрасывания исключений.

Алгоритм 3

Список уникален, если при превращении в множество (set) его размер не изменяется.

         def is_unique3 (alist : [int]) -> bool:   aset = set(alist)               # O(N)   return len(aset) == len(alist)  # O(1)     

Рассчитать класс сложности для всей функции очень просто:

$$O(N)+O(1)=O(N+1)=O(N)$$

Таким образом, третья реализация оказалась самой эффективной из всех с линейным временем выполнения. При увеличении размера списка в два раза, время выполнения функции is_unique3 увеличится всего в два раза.

Тело функции можно записать в одну строчку:

         return len(set(alist)) == len(alist)     

Сложность при этом не изменится.

В отличие от is_unique2, эта реализация может работать и со смешанными списками (числа и строки). В то же время требуется, чтобы все значения были хешируемыми/неизменяемыми. Например, is_unique3 не будет работать для списка списков.

***

Одну проблему можно решить разными способами, из которых одни могут быть эффективнее других. Статический анализ (без запуска кода) позволяет оценить сложность выполнения алгоритмов и функций. Это имеет большое значение для работы с большими наборами данных – чем больше размер входных данных, тем больше выигрыш.

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

Кроме того, при анализе важно учитывать дополнительные ограничения реализации (например, типы данных).

Приоритетные очереди

Рассмотрим еще один важный пример зависимости вычислительной сложности от реализации алгоритма – приоритетные очереди.

Этот тип данных поддерживает две операции:

• добавление значения;
• извлечение значения с самым высоким приоритетом из оставшихся.

Разные реализации приоритетных очередей имеют разные классы сложности этих операций:

Реализация 1

Новое значение добавляется в конец списка (list) или в начала связного списка (linked list) – O(1).

Чтобы найти приоритетное значение для удаления осуществляется поиск по списку – O(N).

Легко добавить, но трудно удалить.

Реализация 2

Для нового значения определяется правильное место – для этого перебираются элементы списка (или связного списка) – O(N).

Зато самое приоритетное значение всегда находится в конце списка (или в начале связного списка) – O(1).

Легко удалить, но трудно добавить.

Реализация 3

Используется двоичная куча, которая позволяет реализовать обе операции со "средней" сложностью O(log N), что для больших значений ближе к O(1), чем к O(N).

Теперь проведем анализ этих реализаций на реальных задачах.

Сортировка

Чтобы отсортировать N значений с помощью приоритетной очереди, нужно сначала добавить все значения в очередь, а затем удалить их все.

Реализация 1

$$N?O(1)+N?O(N)=O(N)+O(N^2)=O(N^2)$$

Реализация 2

$$N?O(N)+N?O(1)=O(N^2)+O(N)=O(N^2)$$

Реализация 3

$$N?O(\log ?N)+N?O(\log ?N)=$$

$$O(N\log ?N)+O(N\log ?N)=O(N\log ?N)$$

Примечание: N * O(...) – это то же самое, что и O(N) * O(...).

Первая и вторая реализации выполняют одну операцию быстро, а другую медленно. В итоге общий класс сложности определяет самая медленная операция.

Третья реализация оказывается быстрее всех, так как ее среднее время O(N log N) ближе к O(1), чем к O(N).

10 максимальных значений

Теперь найдем с помощью приоритетной очереди 10 максимальных значений. Для этого в очередь помещаются N элементов, а извлекаются только 10.

Реализация 1

$$N?O(1)+10?O(N)=O(N)+O(N)=O(N)$$

Реализация 2

$$N?O(N)+10?O(1)=O(N^2)+O(1)=O(N^2)$$

Реализация 3

$$N?O(\log ?N)+10?O(\log ?N)=$$

$$O(N\log ?N)+O(\log ?N)=O(N\log ?N)$$

Теперь первая реализация оказывается самой эффективной, так как операция добавления элемента у нее очень дешевая по времени.

***

Мораль этого примера заключается в том, что иногда не существует "самой лучшей реализации". В зависимости от задачи оптимальными могут быть разные варианты.

А чтобы найти лучшее решение, важно понимать, что такое вычислительная сложность и как ее определить :)