Рубрики

Анализ алгоритмов | Набор 3 (асимптотические обозначения)

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

1) Θ Обозначение: тета-обозначение ограничивает функции сверху и снизу, поэтому оно определяет точное асимптотическое поведение.
Простой способ получить тэта-нотацию выражения — отбросить младшие члены и игнорировать ведущие константы. Например, рассмотрим следующее выражение.
3n 3 + 6n 2 + 6000 = Θ (n 3 )
Отбрасывание членов более низкого порядка всегда хорошо, потому что всегда будет n0, после которого Θ (n 3 ) имеет более высокие значения, чем Θn 2 ), независимо от участвующих констант.
Для данной функции g (n) обозначим Θ (g (n)) следующий набор функций.

Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such 
                 that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}

Вышеприведенное определение означает, что если f (n) является тэтой g (n), то значение f (n) всегда находится между c1 * g (n) и c2 * g (n) для больших значений n (n> = n0). Определение тета также требует, чтобы f (n) была неотрицательной для значений n, превышающих n0.

2) Обозначение Big O: Обозначение Big O определяет верхнюю границу алгоритма, оно ограничивает функцию только сверху. Например, рассмотрим случай сортировки вставкой. Это занимает линейное время в лучшем случае и квадратичное время в худшем случае. Мы можем с уверенностью сказать, что временная сложность сортировки вставкой равна O (n ^ 2). Обратите внимание, что O (n ^ 2) также охватывает линейное время.
Если мы используем обозначение to для представления временной сложности сортировки вставкой, мы должны использовать два оператора для лучшего и худшего случаев:
1. Наихудшая временная сложность сортировки вставкой Θ (n ^ 2).
2. Наилучшая временная сложность сортировки вставкой Θ (n).

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

O(g(n)) = { f(n): there exist positive constants c and 
                  n0 such that 0 <= f(n) <= c*g(n) for 
                  all n >= n0}

3) Обозначение Ω. Так же, как обозначение Big O обеспечивает асимптотическую верхнюю границу функции, обозначение Ω обеспечивает асимптотическую нижнюю границу.

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

Для данной функции g (n) обозначим через Ω (g (n)) множество функций.

Ω (g(n)) = {f(n): there exist positive constants c and
                  n0 such that 0 <= c*g(n) <= f(n) for
                  all n >= n0}.

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

Упражнение:
Какое из следующих утверждений является / является действительным?
1. Сложность времени быстрой сортировки составляет Θ (n ^ 2)
2. Сложность времени быстрой сортировки — O (n ^ 2)
3. Для любых двух функций f (n) и g (n) имеем f (n) = Θ (g (n)) тогда и только тогда, когда f (n) = O (g (n)) и f (n). ) = Ω (g (n)).
4. Временная сложность всех компьютерных алгоритмов может быть записана как Ω (1)

Важные ссылки:

Ссылки:
Лек 1 | MIT (Введение в алгоритмы)

Эта статья предоставлена Абхай Рати . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Анализ алгоритмов | Набор 3 (асимптотические обозначения)

0.00 (0%) 0 votes