Асимптотические обозначения и априорный анализ.
При разработке алгоритма анализ сложности алгоритма является важным аспектом. В основном алгоритмическая сложность связана с ее производительностью, тем, насколько быстро или медленно она работает.
Сложность алгоритма описывает эффективность алгоритма с точки зрения объема памяти, необходимой для обработки данных, и времени обработки.
Сложность алгоритма анализируется с двух точек зрения: 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 это причина того, что мы используем асимптотические обозначения для определения сложности времени и пространства по мере их изменения от компьютера к компьютеру; однако асимптотически они одинаковы.