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

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

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

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

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

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

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

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

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

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

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

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

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

• О — Большой О

• Ω — большая омега

• θ — большая тета

• о — маленький о

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

О — Большой О

Ω — большая омега

θ — большая тета

о — маленький о

ω — маленькая омега

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

«О» (Big Oh) — наиболее часто используемая запись. Функция f (n) может быть представлена ​​в следующем порядке: g (n), то есть O (g (n)) , если существует значение положительного целого числа n, равного n _0, и положительной константы 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))$, когда существуют константы c ₁ и c _2, которые $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-обозначением, может быть или не быть асимптотически жесткой. Оценка $2.n ^ 2 = O (n ^ 2)$ асимптотически тесная, а оценка $2.n = O (n ^ 2)$ — нет.

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

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

Интуитивно понятно, что в o-записи функция 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)$.

ω — обозначение

Мы используем ω-обозначение для обозначения нижней границы, которая не является асимптотически жесткой. Формально, однако, мы определяем ω (g (n)) (мало омега 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)$.

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

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

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

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

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