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

Наверняка вы не раз сталкивались с обозначениями вроде 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 операций в секунду:

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

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

Алгоритм — это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату [1].

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

Содержание:

Читайте также:  315 Или 433mhz что лучше

Модель RAM (Random Access Machine)

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

Модель состоит из памяти и процессора, которые работают следующим образом:

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

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

Подсчет операций. Классы входных данных

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

При выполнении этого алгоритма будет выполнена:

  1. N — 1 операция присваивания счетчику цикла i нового значения;
  2. N — 1 операция сравнения счетчика со значением N;
  3. N — 1 операция сравнения элемента массива со значением min;
  4. от 1 до N операций присваивания значения переменной min.

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

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

  1. исходные данные разбиваются на группы так, что трудоемкость алгоритма ((t_i)) для любого набора данных одной группы одинакова;
  2. исходя из доли наборов данных группы в общем числе наборов, рассчитывается вероятность для каждой группы ((p_i));
  3. оценка среднего случая вычисляется по формуле: (sumlimits_^m p_icdot t_i).

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

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

При анализе скорости роста игнорируются постоянные члены и множители в выражении, т.е. функции (f_x = 10 cdot x^2 + 20 ) и ( g_x = x^2) эквивалентны с точки зрения скорости роста. Незначащие члены лишь добавляют «волнистости», которая затрудняет анализ.

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

  • (mathcal(g)) — функции, растущие медленнее чем g;
  • (Omega(g)) — функции, растущие быстрее чем g;
  • (Theta(g)) — функции, растущие с той же скоростью, что и g.

Запись (f_n = mathcal(g_n)) означает принадлежность функции f классу (mathcal(g)), т.е. функция f ограничена сверху функцией g для достаточно больших значений аргумента. (exists n_0 > 0, c > 0 : forall n > n_0, f_n leq c cdot g_n).

Ограниченность функции g снизу функцией f записывается следующим образом: (g_n =Omega(f_n)). Нотации (Omega) и (mathcal) взаимозаменяемы: (f_n = mathcal(g_n) Leftrightarrow g_n =Omega(f_n)).

Асимптотические обозначения «О большое» и «Омега большое»

Если функции f и g имеют одинаковую скорость роста ((f_n = Theta(g_n))), то существуют положительные константы (c_1) и (c_2) такие, что (exists n_0 > 0 : forall n > n_0, f_n leq c_1 cdot g_n, f_n geq c_2 cdot g_n). При этом (f_n = Theta(g_n) Leftrightarrow g_n = Theta(f_n)).

Асимптотическое обозначение «Тета большое»

Примеры анализа алгоритмов

Алгоритм поиска минимального элемента массива, приведенный выше, выполнит N итераций цикла. Трудоемкость каждой итерации не зависит от количества элементов массива, поэтому имеет сложность (T^ = mathcal(1)). В связи с этим, верхняя оценка всего алгоритма (T^_n = mathcal(n) cdot mathcal(1) = mathcal(n cdot 1) = mathcal(n)). Аналогично вычисляется нижняя оценка сложности, а в силу того, что она совпадает с верхней — можно утверждать (T^_n = Theta(n) ).

Алгоритм пузырьковой сортировки (bubble sort) использует два вложенных цикла. Во внутреннем последовательно сравниваются пары элементов и если оказывается, что элементы стоят в неправильном порядке — выполняется перестановка. Внешний цикл выполняется до тех пор, пока в массиве найдется хоть одна пара элементов, нарушающих требуемый порядок [2].

Читайте также:  Explay pn 430 прошивка

Трудоемкость функции swap не зависит от количества элементов в массиве, поэтому оценивается как (T^ = Theta(1) ). В результате выполнения внутреннего цикла, наибольший элемент смещается в конец массива неупорядоченной части, поэтому через N таких вызовов массив в любом случае окажется отсортирован. Если же массив отсортирован, то внутренний цикл будет выполнен лишь один раз.

В алгоритме сортировки выбором массив мысленно разделяется на упорядоченную и необработанную части. На каждом шаге из неупорядоченной части массива выбирается минимальный элемент и добавляется в отсортированную часть [2].

Для поиска наименьшего элемента неупорядоченной части массива используется функция indMin, принимающая массив, размер массива и номер позиции, начиная с которой нужно производить поиск. Анализ сложности этой функции можно выполнить аналогично тому, как это сделано для функции min — количество операций линейно зависит от количества обрабатываемых элементов: ( T^_ = Theta(n — i)).

У сортировки выбором нет ветвлений, которые могут внести различия в оценку наилучшего и наихудшего случаев, ее трудоемкость: (T^

Математический аппарат анализа алгоритмов

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

Формулы суммирования

В примерах, рассмотренных выше, мы уже сталкивались с нетривиальными формулами суммирования. Чтобы дать оценку суммы можно использовать ряд известных тождеств:

  • вынос постоянного множителя за знак суммы: (sumlimits_^ (c cdot f_i) = c cdot sumlimits_^ cdot f_i);
  • упрощение суммы составного выражения: (sumlimits_^ (f_i + g_i) = sumlimits_^ (f_i) + sumlimits_^ (g_i));
  • сумма чисел арифметической прогрессии: (sumlimits_^ (i^p) = Theta(n^));
  • сумма чисел геометрической прогрессии: (sumlimits_^ (a^i) = frac — 1)>). При ( n o infty ) возможны 2 варианта:
  • если a 1, то сумма стремится к бесконечности: (Theta(a^));
  • если a = 0, формула неприменима, сумма стремится к N: (Theta(n));
  • логарифмическая сложность алгоритма: (sumlimits_^ frac<1>= Theta(log n));
  • сумма логарифмов: (sumlimits_^ log i = Theta(n cdot log n)).
  • Первые из этих тождеств достаточно просты, их можно вывести используя метод математической индукции. Если под знаком суммы стоит более сложная формула, как в двух последних тождествах — суммирование можно заменить интегрированием (взять интеграл функции гораздо проще, ведь для этого существует широкий спектр приемов).

    Суммирование и интегрирование

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

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

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

    На рисунках приведен пример аппроксимации функции (f_x = log x) левыми и правыми прямоугольниками. Очевидно, они дадут верхнюю и нижнюю оценку площади под графиком:

    • (intlimits_a^n f_x dx leq sumlimits_^ f_i leq intlimits_^ f_x dx) для возрастающих функций;
    • (intlimits_a^n f_x dx geq sumlimits_^ f_i geq intlimits_^ f_x dx) для убывающих функций.

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

    Сравнение сложности алгоритмов. Пределы

    Сложность алгоритмов определяется для больших объемов обрабатываемых данных, т.е. при (n oinfty). В связи с этим, при сравнении трудоемкости двух алгоритмов можно рассмотреть предел отношения функций их сложности: (limlimits_ frac ). В зависимости от значения предела возможно сделать вывод относительно скоростей роста функций:

    • предел равен константе и не равен нулю, значит функции растут с одной скоростью:(f_n = Theta(g_n));
    • предел равен нулю, следовательно (g_n) растет быстрее чем (f_n): (f_n = mathcal(g_n));
    • предел равен бесконечности, (g_n) растет медленнее чем (f_n): (f_n = Omega(g_n)).

    Если функции достаточно сложны, то такой прием значительно упрощает задачу, т.к. вместо предела отношения функций можно анализировать предел отношения их производных (согласно правилу Лопиталя): (limlimits_ frac = limlimits_ frac ). Правило Лопиталя можно использовать если функции обладают следующими свойствами:

    Допустим, требуется сравнить эффективность двух алгоритмов с оценками сложности (mathcal(a^n)) и (mathcal(n^b)), где a и b — константы. Известно, что ((c^x)’ =c^x cdot ln(c)), но ((x^c)’ = c cdot x^ ). Применим правило Лопиталя к пределу отношения наших функций b раз, получим: (limlimits_ frac <mathcal(a^n)><mathcal(n^b)> = limlimits_ frac <mathcal(a^n * ln^b (a))><mathcal(b!)> = infty). Значит функция (a^n) имеет более высокую скорость роста. Без использования пределов и правила Лопиталя такой вывод может казаться не очевидным.

    Логарифмы и сложность алгоритмов. Пример

    По определению (log_a = b Leftrightarrow x = a^b). Необходимо знать, что (x o infty Rightarrow log_a o infty), однако, логарифм — это очень медленно растущая функция. Существует ряд формул, позволяющих упрощать выражения с логарифмами:

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

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

    Очевидно, что на каждом шаге алгоритма количество рассматриваемых элементов сокращается в 2 раза. Количество элементов, среди которых может находиться искомый, на k-том шаге определяется формулой (frac<2^k>). В худшем случае поиск будет продолжаться пока в массиве не останется один элемент, т.е. чтобы определить количество итераций для верхней оценки, достаточно решить уравнение (1 = frac <2^k>Rightarrow 2^i = n Rightarrow i = log_2 n). Следовательно, алгоритм имеет логарифмическую сложность: (T^_n = mathcal(log n)).

    Результаты анализа. Замечания. Литература

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

    Анализ алгоритмов позволяет определить минимально возможную трудоемкость, например:

    • алгоритм поиска элемента в неупорядоченном массиве не может иметь верхнюю оценку сложности лучше, чем (mathcal(n)). Это связано с тем, что невозможно определить отсутствие элемента в массиве (худший случай) не просмотрев все его элементы;
    • возможно формально доказать, что не возможен алгоритм сортировки произвольного массива, работающий лучше чем (mathcal(n cdot log n)) [5].

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

    What’s up, программач.
    Любые темы, которые я вижу по алгоритмам, так или иначе касаются их анализа.
    Я понял то, что алгоритмы от N log n типа самые быстрые, n^2 медленнее, и там вроде есть просто N и что-то.
    Что это это такое вообще? Об этом как то слабо упоминается, и предполагается, что читатель знает эти моменты.

    Предположим, что есть число N, которое равно 1 000 000.Во сколько раз алгоритм с показателем N log N будет быстрее алгоритма с показателем N^2?

    Ответ, в 50 000.
    Почему?

    • Вопрос задан более трёх лет назад
    • 5335 просмотров

    Предположим, что есть число N, которое равно 1 000 000.Во сколько раз алгоритм с показателем N log N будет быстрее алгоритма с показателем N^2?

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

    O(1) – затраты времени не зависят от размера задачи
    O(log(n)) – при увеличении размера задачи вдвое, затраты времени меняются на постоянную величину
    O(n) – при увеличении размера задачи в 2 раза, затраты времени возрастут тоже в два раза
    O(n^2) – при увеличении размера задачи в 2 раза, затраты времени возрастут примерно в четыре раза
    O(n*log(n)) – при увеличении задачи в два раза, затраты времени возрастут в два раза, плюс некоторая прибавка, относительный вклад которой уменьшается с ростом n. При малых n может вносить очень большой вклад. O(n*log(n)) начинает расти как квадрат при малых n, но потом рост замедляется почти до линейного
    O(n^p) – полиномиальный алгоритмы, остающиеся мечтой для некоторых задач.
    O(a^n), O(n!), O(n^n) – неполиномиальные алгоритмы, в порядке ускорения увеличения затрат времени

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    Adblock detector