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

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

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

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

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

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

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

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

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

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

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

Функция времени алгоритма представлена 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 1 и 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 это причина, по которой мы используем асимптотические обозначения для определения сложности времени и пространства при их изменении с компьютера на компьютер; однако асимптотически они одинаковы.