Анализ алгоритмов | Обозначение Big – Ω (Big-Omega)

При анализе алгоритмов асимптотические обозначения используются для оценки производительности алгоритма в его лучших и худших случаях. В этой статье мы обсудим нотацию Big – Omega, представленную греческой буквой (Ω).

Определение: Пусть g и f — функция от множества натуральных чисел к самой себе. Функция f называется Ω(g), если существуют константа c > 0 и натуральное число n ₀ такие, что c*g(n) ≤ f(n) для всех n ≥ n ₀

Математическое представление:

Ω(g) = {f(n): there exist positive constants c and n₀ such that 0 ≤ c*g(n) ≤ f(n) for all n ≥ n₀} 
Note: Ω (g) is a set

Графическое представление:

Говоря простым языком, Большой – Омега Обозначение (Ω) определяет асимптотическую (в крайнем случае) нижнюю границу функции f(n).

Выполните следующие шаги, чтобы рассчитать Big – Omega (Ω) для любой программы:

1. Разбейте программу на более мелкие сегменты.
2. Найдите количество операций, выполненных для каждого сегмента (с точки зрения размера входных данных), предполагая, что данные входные данные таковы, что программа занимает наименьшее количество времени.
3. Складываем все операции и упрощаем, допустим, это f(n).
4. Удалите все константы и выберите член с наименьшим порядком или любую другую функцию, которая всегда меньше, чем f (n), когда n стремится к бесконечности, скажем, это g (n), тогда, Big - Omega (Ω) f ( n) есть Ω(g(n)).

Пример: Рассмотрим пример для печати всех возможных пар массива. Идея состоит в том, чтобы запустить два вложенных цикла для генерации всех возможных пар данного массива.

Псевдокод выглядит следующим образом:

int print(int a[], int n)
{
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++)
        {
            if(i != j)
                cout << a[i] << " " 
                     << a[j] << "
";
        }
    }
}

Ниже приведена реализация вышеуказанного подхода:

В этом примере очевидно, что оператор печати выполняется n ² раза, поэтому, если построить график зависимости времени выполнения от n, будет получен параболический график f(n ² ). Теперь линейные функции g(n), логарифмические функции g(log n), константные функции g(1) все меньше, чем параболическая функция, когда диапазон ввода стремится к бесконечности, поэтому время выполнения этой программы в наихудшем случае может быть Ω (log n), Ω(n), Ω(1) или любая функция g(n), которая меньше n ² , когда n стремится к бесконечности. См. графическое представление ниже:

Когда использовать нотацию Big – Ω: Нотация Big – Ω реже всего используется для анализа алгоритмов, потому что она может дать правильное, но неточное утверждение о производительности алгоритма. Предположим, что человеку требуется 100 минут, чтобы выполнить задачу, используя обозначение Ω, можно утверждать, что человеку требуется более 10 минут, чтобы выполнить задачу, это утверждение правильное, но не точное, поскольку в нем не упоминается верхняя граница затраченное время. Точно так же, используя обозначение Ω, мы можем сказать, что время выполнения двоичного поиска в наихудшем случае равно Ω(1), что верно, поскольку мы знаем, что выполнение двоичного поиска потребует, по крайней мере, постоянного времени.

Для получения более подробной информации см.:
Проектирование и анализ алгоритмов.