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

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

Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой.
1. C – константа
2. log(log(N))
3. log(N)
4. N^C, 0<C<1
5. N
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).
Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.
В заключение приведём таблицу, которая показывает, как долго компьютер, осуществляющий миллион операций в секунду, будет выполнять некоторые медленные алгоритмы.

Меpы сложности алгоpитмов (оценка алгоритмов) Понятие сложности

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

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

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

Критерием оптимальности алгоритма выбрана количественная характеристика – сложность алгоритма.

Виды сложностей алгоритма:

Емкостная (пространственная)

Временная

Асимптотическая

Емкостная сложность алгоритма

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

Но память не является критическим ресурсом для современных ВМ.

Временная сложность алгоритма

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

Но одна и та же программа при одних и тех же входных данных на разных ПК будет выполняться разное время. Поэтому измерения не могут быть единицами времени (секунды и т.д.).

т.е. физическое время выполнения алгоритма должно зависеть от количества выполняемых в алгоритме команд и времени их выполнения:

i*t, где

i — число действий (элементарных операций, команд),

элементарные операции – это операции, из которых складывается алгоритм решения задачи (:=, <>, =, +, –, *, /; and, or, not, xor; call, return)

t — среднее время выполнения одного элементарного действия, зависит от скорости обработки сигналов ВМ.

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

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

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

Если размер выхода не превосходит размер входа, то временную сложность можно рассматривать как функцию только размера входных данных.

T(N) — функция временной сложности (трудоемкости) — зависимость времени работы от количества входных данных N – размер задачи.

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

разные операции требуют для своего выполнения разного времени

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

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

Кроме того, точное значение количества операций, выполненных алгоритмом, не играет существенной роли в его анализе, т.к. не является качественным показателем эффективности алгоритма.

Более важной оказывается скорость роста числа выполняемых операций при возрастании объема входных данных.

Два алгоритма можно сравнить по скорости роста сложности алгоритма.

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

Именно эта характеристика часто и фигурирует как оценка вычислительной сложности алгоритма.

Поэтому анализ сложности алгоритма предлагается осуществлять, исследуя как меняется время работы программы при увеличении объема входных данных (N) и с какой скоростью.

Вычислительная сложность алгоритмов по-разному зависит от входных данных:

только от объема данных

От значений данных

От порядка поступления данных

От всех перечисленных выше факторов

Например, многие алгоритмы сортировки потратят гораздо меньше времени на упорядочивание массива, если он уже отсортирован.

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

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

Например, размером входа принято считать:

в задачах обработки одномерных массивов — количество элементов в массиве;

в задачах обработки двумерных массивов — количество элементов в массиве или количество строк и столбцов массива;

в задачах обработки чисел (длинная арифметика, проверка на простоту и т.д.) — общее число битов, необходимое для представления данных в памяти ВМ;

в задачах обработки графов — количество вершин графа или число вершин и число ребер графа.

Т.о. время выполнения алгоритма T зависит от объема входных данных N:

где T – время выполнения алгоритма, мс;

Для построения аналитической зависимости скорости роста:

оценивают функцию T(N) при некотором интервале [Nmin, Nmax]

Проводят аппроксимацию этой кривой с помощью некоторой аналитической функции f(N), поведение которой хорошо исследовано

Изменяют параметры функции и оценивают ошибки аппроксимации.

По виду функции f(N) алгоритмы разделяются на следующие классы:

С линейной оценкой сложности, если функция f(N) = C· N ;

С квадратичной сложностью, если

f(N) = C · N 2 ;

С полиномиальной сложностью, если

f(N) = C₀ + C₁· N +…+ C_k · N k ;

С факториальной сложностью, если f(N) =C· N!;

С экспоненциальной сложностью, если f(N) = C · a N ;

С гиперэкспоненциальной сложностью, если f(N) = C · a t, где t = a N .

Здесь C, a и k = некоторые константы, при этом число C может быть очень большим.

Сложность алгоритмов. Big O. Основы.

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

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

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

Тогда было предложено измерять сложность алгоритмов в элементарных шагах — то, сколько действий необходимо совершить для его выполнения. Любой алгоритм включает в себя определённое количество шагов и не важно на каком устройстве он будет запущен, количество шагов останется неизменным. Эту идею принято представлять в виде Big O (или О-нотации).

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

Big O показывает верхнюю границу зависимости между входными параметрами функции и количеством операций, которые выполнит процессор.

Распространённые сложности алгоритмов

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

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

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

Пример № 1.

У нас есть массив из 5 чисел и нам надо получить первый элемент.

Насколько возрастет количество операций при увеличении размера входных параметров?
Нинасколько. Даже если массив будет состоять из 100, 1000 или 10 000 элементов нам всеравно потребуется одна операция.

Пример № 2.

Сложение двух чисел. Функция всегда выполняет константное количество операций.

Пример № 3.

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

Линейная — O(n).

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

Такие алгоритмы легко узнать по наличию цикла по каждому элементу массива.

Пример № 1 — Рекурсивная функция.

Пример № 2 — Линейная функция.

Функция pairSumSequence() в цикле складывает какие-либо пары чисел, вызывая функцию pairSum() . Цикл выполняется от 0 до n. Т.е. чем больше n, тем больше раз выполнится цикл. Поэтому сложность функции pairSumSequence() — O(n).

Пример № 3.

В функции два последовательных цикла for , каждый из которых проходит массив длиной n, следовательно сложность будет: O(n + n) = O(n)

Логарифмическая — O(log n).

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

К алгоритмам с такой сложностью относятся алгоритмы типа “Разделяй и Властвуй” (Divide and Conquer), например бинарный поиск.

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

Означает, что удвоение размера входных данных увеличит время выполнения чуть более, чем вдвое.

Примеры алгоритмов с такой сложностью: Сортировка слиянием или множеством n элементов.

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

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

Такие алгоритмы легко узнать по вложенным циклам.

Пример № 1.

В функции есть цикл в цикле, каждый из них проходит массив длиной n, следовательно сложность будет: O(n * n) = O(n 2 )

Зачем изучать Big O

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

Шпаргалка

Небольшие подсказки, которые помогут определить сложность алгоритма.

• Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1).
• Перебор коллекции это O(n).
• Вложенные циклы по той же коллекции это O(n 2 ).
• Разделяй и властвуй (Divide and Conquer) всегда O(log n).
• Итерации которые используют “Разделяй и властвуй” (Divide and Conquer) это O(n log n).

Полезные ссылки

Оценка сложности алгоритма. Сложность алгоритмов. Big O, Большое О — 25-минутное видео, в котором очень доступно (и с примерами) объясняются основы анализа сложности алгоритмов.
Big O — статья на хабре о Big O.
Знай сложности алгоритмов — статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов.

Оценка сложности алгоритмов, или Что такое О(log n)

Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы хотите стать хорошим программистом, но так и не понимаете, что это значит, — данная статья для вас.

Оценка сложности

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

Допустим, некоторому алгоритму нужно выполнить 4n 3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n 3 ) , т. е. зависит от размера входных данных кубически.

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

Примеры

O(n) — линейная сложность

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

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n 2 ) — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n 2 .

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

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

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

Наглядно

Время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при скорости 10 6 операций в секунду:

Тут можно посмотреть сложность основных алгоритмов сортировки и работы с данными.

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