Во время своей работы программы используют различные структуры данных и алгоритмы, в связи с чем обладают разной эффективностью и скоростью решения задачи. Дать оценку оптимальности решения, реализованного в программе, поможет понятие вычислительной сложности алгоритмов.
6.1.1. Основные понятия¶
Вычислительная сложность (алгоритмическая сложность) — понятие, обозначающее функцию зависимости объема работы алгоритма от размера обрабатываемых данных.
Вычислительная сложность пытается ответить на центральный вопрос разработки алгоритмов: как изменится время исполнения и объем занятой памяти в зависимости от размера входных данных?. С помощью вычислительной сложности также появляется возможность классификации алгоритмов согласно их производительности.
В качестве показателей вычислительной сложности алгоритма выступают:
Временная сложность (время выполнения).
Временная сложность алгоритма — это функция от размера входных данных, равная количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.
Временная сложность алгоритма зачастую может быть определена точно, однако в большинстве случаев искать точное ее значение бессмысленно, т.к. работа алгоритма зависит от ряда факторов, например, скорости процессора, набора его инструкций и т.д.
Асимптотическая сложность оценивает сложность работы алгоритма с использованием асимптотического анализа.
Алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных.
О-нотация, \(O\) («О»-большое): описывает верхнюю границу времени (время выполнения «не более, чем…»);
Омега-нотация, \(\Omega\) («Омега»-большое): описывает нижнюю границу времени (время выполнения «не менее, чем…»).
говорит о том, что алгоритм имеет квадратичное время выполнения относительно размера входных данных в качестве верхней оценки («О большое от эн квадрат»).
Каждая оценка при этом может быть:
наилучшая: минимальная временная оценка;
наихудшая: максимальная временная оценка;
средняя: средняя временная оценка.
При оценке, как правило, указывается наихудшая оценка.
Допустим, имеется задача поиска элемента в массиве. При полном переборе слева направо:
наилучшая оценка: \(O(1)\) , если искомый элемент окажется в начале списка;
наихудшая оценка: \(O(N)\) , если искомый элемент окажется в конце списка;
Наиболее часто используемой оценкой сложности алгоритма является верхняя (наихудшая) оценка, которая обычно выражается с использованием нотации O-большое.
Выделяют следующие основные категории алгоритмической сложности в \(O\) -нотации:
Постоянное время: \(O(1)\) .
Время выполнения не зависит от количества элементов во входном наборе данных.
Пример: операции присваивания, сложения, взятия элемента списка по индексу и др.
Линейное время: \(O(N)\) .
Время выполнения пропорционально количеству элементов в коллекции.
Пример: найти имя в телефонной книге простым перелистыванием, почистить ковер пылесосом и т.д.
Логарифмическое время: \(O(\log)\) .
Время выполнения пропорционально логарифму от количества элементов в коллекции.
Пример: найти имя в телефонной книге (используя двоичный поиск).
Линейно-логарифмическое время: \(O(N \log)\) .
Время выполнения больше чем, линейное, но меньше квадратичного.
Время выполнения пропорционально квадрату количества элементов в коллекции.
Пример: вложенные циклы (сортировка, перебор делителей и т.д.).
На Рисунке 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).
Таблица 6.1.1 — Асимптотические сложности для списка или кортежа ¶
Сколько стоят операции над 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. Можно использовать списки для создания стека или очереди. Списки — это упорядоченные и изменяемые коллекции, которые можно обновлять по желанию.
Множества также являются одними из наиболее используемых типов данных в 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).
Понимание сложности времени на примерах Python
В настоящее время со всеми этими данными, которые мы потребляем и генерируем каждый день, алгоритмы должны быть достаточно хороши для обработки операций с большими объемами данных.
В этом посте мы немного больше узнаем о сложности времени, нотации Big-O и о том, почему мы должны заботиться об этом при разработке алгоритмов.
Примеры, показанные в этой истории, были разработаны на Python, поэтому вам будет легче понять, если у вас есть хотя бы базовые знания Python, но это не является обязательным условием.
Давайте начнем понимать, что такое вычислительная сложность.
Вычислительная сложность
Вычислительная сложностьэто область из информатики, котораяанализирует алгоритмы на основе количества ресурсов, необходимых для его запуска, Количество требуемых ресурсов зависит от размера входных данных, поэтому сложность обычно выражается как функцияN, гдеNэто размер ввода.
Важно отметить, что при анализе алгоритма мы можем рассмотретьсложность времениа такжесложность пространства, Сложность пространства — это, в основном, объем памяти, необходимый для решения проблемы, связанной с размером ввода. Несмотря на то, что сложность пространства важна при анализе алгоритма, в этой истории мы сосредоточимся только на сложности времени.
Сложность времени
Поскольку вы читаете эту историю прямо сейчас, у вас может быть представление о том, что такое сложность времени, но чтобы убедиться, что мы все на одной странице, давайте начнем понимать, что означает сложность времени, с помощью краткого описания отВикипедия,
В информатике сложность времени — это сложность вычислений, которая описывает количество времени, которое требуется для запуска алгоритма. Временная сложность обычно оценивается путем подсчета количества элементарных операций, выполняемых алгоритмом, предполагая, что каждая элементарная операция занимает фиксированное количество времени для выполнения.
При анализе временной сложности алгоритма мы можем найти три случая:лучший случай,в среднем случаеа такжехудший случай, Давайте разберемся, что это значит.
Предположим, у нас есть следующий несортированный список[1, 5, 3, 9, 2, 4, 6, 7, 8]и нам нужно найти индекс значения в этом списке, используялинейный поиск,
лучший случай: это сложность решения проблемы для лучшего ввода. В нашем примере лучшим вариантом будет поиск значения 1. Поскольку это первое значение в списке, оно будет найдено в первой итерации.
в среднем случае: это средняя сложность решения проблемы. Эта сложность определяется в отношении распределения значений во входных данных. Возможно, это не лучший пример, но, основываясь на нашем примере, мы могли бы сказать, что средний случай будет, когда мы ищем какое-то значение в «середине» списка, например, значение 2.
худший случай: это сложность решения задачи для худшего ввода размера n. В нашем примере наихудшим вариантом будет поиск значения 8, которое является последним элементом в списке.
Обычно, описывая временную сложность алгоритма, мы говорим о худшем случае.
Хорошо, но как мы описываем временную сложность алгоритма?
Мы используем математическую запись под названием Big-O.
Биг-О нотация
Биг-О нотацияиногда называют «асимптотической нотацией»,это математическая запись, которая описывает ограничивающее поведение функциикогда аргумент стремится к определенному значению или бесконечности.
В информатике нотация Big-O используется для классификации алгоритмов в соответствии с тем, как их требования к времени выполнения или пространству растут по мере увеличения размера ввода (N) растет. Это обозначение характеризует функции в соответствии с их темпами роста: различные функции с одинаковой скоростью роста могут быть представлены с использованием одинаковых обозначений O.
Давайте посмотрим некоторые общие временные сложности, описанные в нотации Big-O.
Таблица общих временных сложностей
Это наиболее распространенные временные сложности, выраженные с помощью нотации Big-O:
Обратите внимание, что мы сосредоточим наше исследование на этих общих временных сложностях, но есть некоторые другие временные сложности, которые вы можете изучить позже.
Как уже было сказано, мы обычно используем нотацию Big-O для описания временной сложности алгоритмов. В формальном определении нотации много математики, но неформально мы можем предположить, что нотация Big-O дает нам приблизительное время выполнения алгоритма в худшем случае. При использовании обозначения Big-O мы описываем эффективность алгоритма на основе увеличения размера входных данных (N). Например, если вход является строкой,Nбудет длина строки. Если это список, тоNбудет длина списка и так далее.
Теперь давайте рассмотрим каждую из этих общих временных сложностей и рассмотрим несколько примеров алгоритмов. Обратите внимание, что я попытался следовать следующему подходу: представить небольшое описание, показать простой и понятный пример и показать более сложный пример (обычно из реальной проблемы).
Сложности времени
Постоянное время — O (1)
Говорят, что алгоритм имеет постоянное время, когда он не зависит от входных данных (N). Независимо от размера входных данных, время выполнения всегда будет одинаковым. Например:
Теперь давайте посмотрим на функциюget_firstкоторый возвращает первый элемент списка:
Независимо от размера входных данных, он всегда будет иметь одинаковое время выполнения, поскольку он получает только первое значение из списка.
Алгоритм с постоянной сложностью времени превосходен, так как нам не нужно беспокоиться о размере ввода.
Логарифмическое время — O (log n)
Говорят, что алгоритм имеет сложность логарифмического времени, когда он уменьшает размер входных данных на каждом шаге (ему не нужно просматривать все значения входных данных), например:
Алгоритмы с логарифмической сложностью времени обычно встречаются в операциях надбинарные деревьяили при использованиибинарный поиск, Давайте посмотрим на пример бинарного поиска, где нам нужно найти позицию элемента в отсортированном списке:
Шаги бинарного поиска:
Рассчитайте середину списка.
Если искомое значение меньше, чем значение в середине списка, установите новую правую границу.
Если искомое значение больше, чем значение в середине списка, установите новую левую направляющую.
Если значение поиска равно значению в середине списка, вернуть середину (индекс).
Повторяйте шаги, описанные выше, пока значение не будет найдено или левая отметка не станет равной или выше правой отметки.
Важно понимать, что алгоритм, который должен обращаться ко всем элементам своих входных данных, не может занимать логарифмическое время, так как время, затрачиваемое на чтение входных данных размераNимеет порядокN,
Линейное время — O (n)
Говорят, что алгоритм имеет линейную сложность по времени, когда время работы увеличивается максимально линейно с размером входных данных. Это наилучшая временная сложность, когда алгоритм должен проверять все значения во входных данных. Например:
Давайте посмотрим на примерлинейный поискгде нам нужно найти позицию элемента в несортированном списке:
Обратите внимание, что в этом примере нам нужно просмотреть все значения в списке, чтобы найти искомое значение.
Квазилинейное время — O (n log n)
Говорят, что алгоритм имеет квазилинейную временную сложность, когда каждая операция во входных данных имеет логарифмическую временную сложность. Это обычно видно в алгоритмах сортировки (например,Сортировка слиянием,timsort,пирамидальная сортировка).
Например: для каждого значения в data1 (На)) использовать бинарный поиск (O (log n)) искать то же значение в data2.
Другой, более сложный пример, можно найти вСортировка слияниемалгоритм. Mergesort — это эффективный универсальный алгоритм сортировки на основе сравнения, который имеет квазилинейную сложность по времени, давайте рассмотрим пример:
Следующее изображение иллюстрирует шаги, предпринятые алгоритмом сортировки слиянием.
Обратите внимание, что в этом примере сортировка выполняется на месте.
Квадратичное время — O (n²)
Говорят, что алгоритм имеет квадратичную сложность по времени, когда ему необходимо выполнить линейную операцию по времени для каждого значения во входных данных, например:
Пузырьковая сортировкаявляется отличным примером квадратичной временной сложности, поскольку для каждого значения, которое необходимо сравнить со всеми другими значениями в списке, давайте рассмотрим пример:
Экспоненциальное время — O (2 ^ n)
Говорят, что алгоритм имеет экспоненциальную временную сложность, когда рост удваивается с каждым добавлением к набору входных данных. Этот вид временной сложности обычно проявляется в алгоритмах перебора.
В качестве примера можно привести Вики Лай:
В криптографии атака методом «грубой силы» может систематически проверять все возможные элементы пароля путем перебора подмножеств. Используя экспоненциальный алгоритм для этого, становится невероятно дорогостоящим взламывать и взламывать длинный пароль вместо более короткого. Это одна из причин того, что длинный пароль считается более безопасным, чем более короткий.
Другим примером экспоненциального алгоритма времени является рекурсивный расчетФибоначчиномера:
Если вы не знаете, чторекурсивная функцияесть, давайте проясним это быстро: рекурсивная функция может быть описана как функция, которая вызывает себя в определенных условиях. Как вы, возможно, заметили, временную сложность рекурсивных функций определить немного сложнее, поскольку она зависит от того, сколько раз вызывается функция и от временной сложности одного вызова функции.
Это имеет больше смысла, когда мы смотрим на дерево рекурсии Следующее дерево рекурсии было сгенерировано алгоритмом Фибоначчи с использованиемn = 4:
Обратите внимание, что он будет называть себя, пока не достигнет листьев. При достижении листьев он возвращает само значение.
Теперь посмотрите, как растет дерево рекурсии, просто увеличиваяNдо 6:
Вы можете найти более полное объяснение временной сложности рекурсивного алгоритма ФибоначчиВотна StackOverflow.
Факториал — O (n!)
Говорят, что алгоритм имеет факторную сложность времени, когда он растет факториальным образом в зависимости от размера входных данных, например:
Как вы можете видеть, он очень быстро растет даже при небольшом входном размере.
Отличным примером алгоритма, который имеет сложность факторного времени, является алгоритм Heap, который используется для генерации всех возможных перестановокNобъекты.
Хип нашел систематический метод для выбора на каждом шаге пары элементов для переключения, чтобы произвести каждую возможную перестановку этих элементов ровно один раз.
Давайте посмотрим на пример:
Обратите внимание, что он будет расти факториальным образом, в зависимости от размера входных данных, поэтому мы можем сказать, что алгоритм имеет факторную сложность времени O (n!).
Еще один замечательный примерЗадача коммивояжера,
Важные заметки
Важно отметить, что при анализе временной сложности алгоритма с несколькими операциями нам необходимо описать алгоритм на основе наибольшей сложности среди всех операций. Например:
Даже если операции в «my_function» не имеют смысла, мы видим, что он имеет несколько временных сложностей: O (1) + O (n) + O (n²). Таким образом, при увеличении размера входных данных узким местом этого алгоритма будет операция, которая принимает O (n²). Исходя из этого, мы можем описать временную сложность этого алгоритма как O (n²).
Шпаргалка Big-O
Чтобы сделать вашу жизнь проще, здесь вы можете найти лист с временной сложностью операций в наиболее распространенных структурах данных.
Вот еще один лист со сложностью времени наиболее распространенных алгоритмов сортировки.
Почему важно знать все это?
Если после прочтения всей этой истории у вас все еще есть сомнения относительно важности понимания сложности времени и обозначения Big-O, давайте уточним некоторые моменты.
Даже при работе с современными языками, такими как Python, который предоставляет встроенные функции, такие как алгоритмы сортировки, когда-нибудь вам, вероятно, потребуется реализовать алгоритм для выполнения некоторой операции с определенным объемом данных. Изучая сложность времени, вы поймете важную концепцию эффективности и сможете найти узкие места в вашем коде, которые следует улучшить, главным образом при работе с огромными наборами данных.
Кроме того, если вы планируете подать заявку на должность инженера-программиста в такой крупной компании, как Google, Facebook, Twitter и Amazon, вам нужно быть готовым ответить на вопросы о сложности времени, используя нотацию Big-O.
Заключительные заметки
Спасибо за чтение этой истории. Я надеюсь, что вы узнали немного больше о сложности времени и нотации Big-O. Если вам понравилось, пожалуйста, хлопните в ладоши и поделитесь им. Если у вас есть какие-либо сомнения или предложения, не стесняйтесь комментировать или отправить мне письмо. Кроме того, не стесняйтесь следовать за мной нащебет,Linkedin, а такжеGithub,
Есть ли способ автоматически вывести сложность алгоритма (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)) на этих входных данных, что неверно.
Можно написать что-то тупое и наивное, вроде подсчета количества вложенных циклов, но работать будет только в очень частных случаях и часто ошибаться.
