Как определить сложность алгоритма python

Есть ли способ автоматически вывести сложность алгоритма (Python)?

Нет нельзя. Потому что нельзя даже определить, завершается ли программа, или виснет. Это называется проблема остановки (https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D. Логически доказано, что невозможно автоматически решить ее.

Подобным образом можно доказать, что не существует программы, определяющей сложность любой программы.
Допустим, что такая программа есть. Напишем другую программу, которая анализирует входной исходный код этой первой программой (пусть она получила оценку f(N)), а потом делает что-то неважное (например прибавляет 1 к переменной) f(N)*N раз. Теперь запустим эту программу на собственном исходном коде. Она получит оценку своей сложности и потом сделает что-то в N раз больше. Т.е. фактически сделано f(N)*N операций, но программа же оценила этот код как O(f(N)) на этих входных данных, что неверно.

Можно написать что-то тупое и наивное, вроде подсчета количества вложенных циклов, но работать будет только в очень частных случаях и часто ошибаться.

6.1. Теория¶

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

6.1.1. Основные понятия¶

Вычислительная сложность (алгоритмическая сложность) — понятие, обозначающее функцию зависимости объема работы алгоритма от размера обрабатываемых данных.

Вычислительная сложность пытается ответить на центральный вопрос разработки алгоритмов: как изменится время исполнения и объем занятой памяти в зависимости от размера входных данных?. С помощью вычислительной сложности также появляется возможность классификации алгоритмов согласно их производительности.

В качестве показателей вычислительной сложности алгоритма выступают:

Временная сложность (время выполнения).

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

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

Асимптотическая сложность оценивает сложность работы алгоритма с использованием асимптотического анализа.

Алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных.

6.1.2. Асимптотические нотации¶

Асимптотическая сложность алгоритма описывается соответствующей нотацией:

О-нотация, \(O\) («О»-большое): описывает верхнюю границу времени (время выполнения «не более, чем…»);

Омега-нотация, \(\Omega\) («Омега»-большое): описывает нижнюю границу времени (время выполнения «не менее, чем…»).

говорит о том, что алгоритм имеет квадратичное время выполнения относительно размера входных данных в качестве верхней оценки («О большое от эн квадрат»).

Каждая оценка при этом может быть:

наилучшая: минимальная временная оценка;

наихудшая: максимальная временная оценка;

средняя: средняя временная оценка.

При оценке, как правило, указывается наихудшая оценка.

Допустим, имеется задача поиска элемента в массиве. При полном переборе слева направо:

наилучшая оценка: \(O(1)\) , если искомый элемент окажется в начале списка;

наихудшая оценка: \(O(N)\) , если искомый элемент окажется в конце списка;

средняя оценка: \(O \left ( \cfrac <2>\right ) = O(N)\) .

6.1.2.1. Верхняя оценка и \(O\) -нотация¶

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

Выделяют следующие основные категории алгоритмической сложности в \(O\) -нотации:

Постоянное время: \(O(1)\) .

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

• Пример: операции присваивания, сложения, взятия элемента списка по индексу и др.

Линейное время: \(O(N)\) .

• Время выполнения пропорционально количеству элементов в коллекции.

• Пример: найти имя в телефонной книге простым перелистыванием, почистить ковер пылесосом и т.д.

Логарифмическое время: \(O(\log)\) .

• Время выполнения пропорционально логарифму от количества элементов в коллекции.

• Пример: найти имя в телефонной книге (используя двоичный поиск).

Линейно-логарифмическое время: \(O(N \log)\) .

• Время выполнения больше чем, линейное, но меньше квадратичного.

• Пример: обработка \(N\) телефонных справочников двоичным поиском.

Квадратичное время: \(O(N^<2>)\) .

• Время выполнения пропорционально квадрату количества элементов в коллекции.

• Пример: вложенные циклы (сортировка, перебор делителей и т.д.).

На Рисунке 6.1.1 приведен график роста \(O\) -большое.

Рисунок 6.1.1 — График роста \(O\) -большое 6 ¶

6.1.3. Оценка сложности алгоритмов¶

Для оценки вычислительной сложности алгоритмов необходимо знать и учитывать сложности:

используемых структур данных;

совокупности различных операций.

6.1.3.1. Операции над структурами данных¶

В Python имеются коллекции (структуры данных), операции над которыми имеют определенную сложность.

6.1.3.1.1. Список и кортеж¶

Большинство операций со списком/кортежем имеют сложность \(O(N)\) (Таблица 6.1.1).

collections.deque

A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.

See dict — the implementation is intentionally very similar.

The Average Case times listed for dict objects assume that the hash function for the objects is sufficiently robust to make collisions uncommon. The Average Case assumes the keys used in parameters are selected uniformly at random from the set of all keys.

Note that there is a fast-path for dicts that (in practice) only deal with str keys; this doesn’t affect the algorithmic complexity, but it can significantly affect the constant factors: how quickly a typical program finishes.

Notes

[1] = These operations rely on the «Amortized» part of «Amortized Worst Case». Individual actions may take surprisingly long, depending on the history of the container.

[2] = Popping the intermediate element at index k from a list of size n shifts all elements after k by one slot to the left using memmove. n — k elements have to be moved, so the operation is O(n — k). The best case is popping the second to last element, which necessitates one move, the worst case is popping the first element, which involves n — 1 moves. The average case for an average value of k is popping the element the middle of the list, which takes O(n/2) = O(n) operations.

[3] = For these operations, the worst case n is the maximum size the container ever achieved, rather than just the current size. For example, if N objects are added to a dictionary, then N-1 are deleted, the dictionary will still be sized for N objects (at least) until another insertion is made.

Сколько стоят операции над list, set и dict в Python? Разбираемся с временной сложностью

Программисту, работающему с данными, крайне важно выбирать правильные структуры данных для решения поставленной задачи, ведь выбор неправильного типа данных плохо влияет на производительность приложения. В этой статье объясняется нотация «О» большое и сложность ключевых операций структур данных в CPython.

Что означает нотация «O» большое?

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

«O» большое служит обозначением временной сложности операций алгоритма. Она показывает, сколько времени потребуется алгоритму для вычисления требуемой операции. Можно также измерить пространственную сложность (сколько места занимает алгоритм), но в этой статье мы сосредоточимся на временной.

Проще говоря, нотация «O» большое — это способ измерения производительности операции на основе размера ввода, известного как n.

Значения нотации «О» большое

На письме временная сложность алгоритма обозначается как O(n), где n — размер входной коллекции.

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

O(log n)

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

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

O(n log n)

Обозначение квазилинейной временной сложности. Скорость выполнения операции является квазилинейной функцией числа элементов в коллекции. Временная сложность оптимизированного алгоритма сортировки обычно равна O(n log n).

O(n^2)

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

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

Нотация «O» большое относительна. Она не зависит от машины, игнорирует константы и понятна широкой аудитории, включая математиков, технологов, специалистов по данным и т. д.

Благоприятные, средние и худшие случаи

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

Благоприятный случай. Как следует из названия, это сценарий, когда структуры данных и элементы в коллекции вместе с параметрами находятся в оптимальном состоянии. Например, мы хотим найти элемент в коллекции. Если этот элемент оказывается первым элементом коллекции, то это лучший сценарий для операции.

Средний случай. Определяем сложность на основе распределения значений входных данных.

Худший случай. Структуры данных и элементы в коллекции вместе с параметрами находятся в наиболее неоптимальном состоянии. Например, худший случай для операции, которой требуется найти элемент в большой коллекции в виде списка — когда искомый элемент находится в самом конце, а алгоритм перебирает коллекцию с самого начала.

Коллекции Python и их временная сложность

Список (list)

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

Операции списка и их временная сложность

Вставка: O(n).
Получение элемента: O(1).
Удаление элемента: O(n).
Проход: O(n).
Получение длины: O(1).

Множество (set)

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

Операции с множествами и их временная сложность

Проверить наличие элемента в множестве: O(1).
Отличие множества A от B: O(длина A).
Пересечение множеств A и B: O(минимальная длина A или B).
Объединение множеств A и B: O(N) , где N это длина (A) + длина (B).

Словарь (dict)

Словарь — это коллекция пар ключ-значение. Ключи в словаре уникальны, чтобы предотвратить коллизию элементов. Это чрезвычайно полезная структура данных.

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

Операции со словарями и их временная сложность

Здесь мы считаем, что ключ используется для получения, установки или удаления элемента.

Получение элемента: O(1).
Установка элемента: O(1).
Удаление элемента: O(1).
Проход по словарю: O(n).