Асимптотические обозначения и априорный анализ.

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

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

Сложность алгоритма анализируется с двух точек зрения: Time а также Space.

Сложность времени

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

Космическая сложность

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

Сложность пространства иногда игнорируется, потому что используемое пространство минимально и / или очевидно, однако иногда это становится такой же важной проблемой, как время.

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

Время выполнения алгоритма зависит от набора команд, скорости процессора, скорости дискового ввода-вывода и т. Д. Следовательно, мы оцениваем эффективность алгоритма асимптотически.

Функция времени алгоритма представлена ​​как T(n), где n - размер ввода.

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

  • O - Большой О

  • Ω - Большая омега

  • θ - Большая тета

  • o - Маленький О

  • ω - Маленькая омега

O: асимптотическая верхняя граница

«О» (Большое О) - наиболее часто используемое обозначение. Функцияf(n) может быть представлен в порядке g(n) то есть O(g(n)), если существует положительное целое число n в качестве n0 и положительная постоянная c такой, что -

$ f (n) \ leqslant cg (n) $ для $ n> n_ {0} $ во всех случаях

Следовательно, функция g(n) является верхней границей функции f(n), в качестве g(n) растет быстрее, чем f(n).

пример

Рассмотрим заданную функцию, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Учитывая $ g (n) = n ^ 3 $,

$ f (n) \ leqslant 5.g (n) $ для всех значений $ n> 2 $

Следовательно, сложность f(n) можно представить как $ O (g (n)) $, т.е. $ O (n ^ 3) $

Ω: асимптотическая нижняя граница

Мы говорим, что $ f (n) = \ Omega (g (n)) $, когда существует постоянная c что $ f (n) \ geqslant cg (n) $ для всех достаточно больших значений n. Вотnположительное целое число. Это означает функциюg оценка снизу функции f; после определенного значенияn, f никогда не пойдет ниже g.

пример

Давайте рассмотрим заданную функцию, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.

Учитывая, что $ g (n) = n ^ 3 $, $ f (n) \ geqslant 4.g (n) $ для всех значений $ n> 0 $.

Следовательно, сложность f(n) можно представить как $ \ Omega (g (n)) $, т.е. $ \ Omega (n ^ 3) $

θ: асимптотическая жесткая граница

Мы говорим, что $ f (n) = \ theta (g (n)) $, когда существуют константы c1 а также c2 что $ c_ {1} .g (n) \ leqslant f (n) \ leqslant c_ {2} .g (n) $ для всех достаточно больших значений n. Вотn положительное целое число.

Это означает функцию g является точной оценкой для функции f.

пример

Рассмотрим заданную функцию, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Учитывая, что $ g (n) = n ^ 3 $, $ 4.g (n) \ leqslant f (n) \ leqslant 5.g (n) $ для всех больших значений n.

Следовательно, сложность f(n) можно представить как $ \ theta (g (n)) $, т.е. $ \ theta (n ^ 3) $.

O - обозначение

Асимптотическая оценка сверху, полученная с помощью O-notationможет быть или не быть асимптотически жестким. Оценка $ 2.n ^ 2 = O (n ^ 2) $ асимптотически точна, а оценка $ 2.n = O (n ^ 2) $ - нет.

Мы используем o-notation для обозначения верхней границы, которая не является асимптотически точной.

Формально определяем o(g(n)) (немного о г из п) как набор f(n) = o(g(n)) для любой положительной константы $ c> 0 $ и существует значение $ n_ {0}> 0 $ такое, что $ 0 \ leqslant f (n) \ leqslant cg (n) $.

Интуитивно в o-notation, функция f(n) становится несущественным по отношению к g(n) в качестве nприближается к бесконечности; то есть,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = 0 $$

пример

Рассмотрим ту же функцию, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $.

Учитывая, что $ g (n) = n ^ {4} $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 4} \ right) = 0 $$

Следовательно, сложность f(n) можно представить как $ o (g (n)) $, т.е. $ o (n ^ 4) $.

ω - Обозначение

Мы используем ω-notationдля обозначения нижней границы, которая не является асимптотически точной. Формально, однако, определимω(g(n)) (мало-омега г н) как набор f(n) = ω(g(n)) для любой положительной постоянной C > 0 и существует значение $ n_ {0}> 0 $ такое, что $ 0 \ leqslant cg (n) <f (n) $.

Например, $ \ frac {n ^ 2} {2} = \ omega (n) $, но $ \ frac {n ^ 2} {2} \ neq \ omega (n ^ 2) $. Из соотношения $ f (n) = \ omega (g (n)) $ следует, что существует следующий предел

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {f (n)} {g (n)} \ right) = \ infty $$

То есть, f(n) становится сколь угодно большим относительно g(n) в качестве n приближается к бесконечности.

пример

Рассмотрим ту же функцию, $ f (n) = 4.n ^ 3 + 10.n ^ 2 + 5.n + 1 $

Учитывая, что $ g (n) = n ^ 2 $,

$$ \ lim_ {n \ rightarrow \ infty} \ left (\ frac {4.n ^ 3 + 10.n ^ 2 + 5.n + 1} {n ^ 2} \ right) = \ infty $$

Следовательно, сложность f(n) можно представить как $ o (g (n)) $, т.е. $ \ omega (n ^ 2) $.

Априори и апостиарный анализ

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

Анализ алгоритма апостиари означает, что мы выполняем анализ алгоритма только после его запуска в системе. Это напрямую зависит от системы и меняется от системы к системе.

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

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