algorithm
Сложность алгоритма

замечания

total = 0
for(i = 1; i < 10; i++)
    total = total + i

Обозначение Big-Theta

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

Обозначение Big-Theta симметрично: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

Интуитивно понятный способ понять это состоит в том, что f(x) = Ө(g(x)) означает, что графики f (x) и g (x) растут с той же скоростью или что графики «ведут себя» аналогично для больших достаточно значений х.

Полное математическое выражение нотации Большого тета выглядит следующим образом:
Ө (f (x)) = {g: N ₀ -> R и c ₁ , c ₂ , n ₀ > 0, где c ₁ <abs (g (n) / f (n)), для любого n> n _0, а абс - абсолютное значение}

Пример

Если алгоритм для ввода n 42n^2 + 25n + 4 операций, мы говорим, что O(n^2) , но также O(n^3) и O(n^100) . Однако это Ө(n^2) и это не Ө(n^3) , Ө(n^4) и т. Д. Алгоритм Ө(f(n)) также O(f(n)) , но не наоборот!

Формальное математическое определение

Ө(g(x)) - множество функций.

Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}

Поскольку Ө(g(x)) является множеством, мы могли бы написать f(x) ∈ Ө(g(x)) чтобы указать, что f(x) является членом Ө(g(x)) . Вместо этого мы обычно будем писать f(x) = Ө(g(x)) чтобы выразить одно и то же понятие - это общий путь.

Всякий раз, когда Ө(g(x)) появляется в формуле, мы интерпретируем ее как стоящую за какую-то анонимную функцию, которую мы не хотим называть. Например, уравнение T(n) = T(n/2) + Ө(n) означает T(n) = T(n/2) + f(n) где f(n) - функция из множества Ө(n) .

Пусть f и g - две функции, определенные на некотором подмножестве вещественных чисел. Запишем f(x) = Ө(g(x)) как x->infinity тогда и только тогда, когда существуют положительные константы K и L и вещественное число x0 такое, что выполнено:

K|g(x)| <= f(x) <= L|g(x)| для всех x >= x0 .

Определение равно:

f(x) = O(g(x)) and f(x) = Ω(g(x))

Метод, который использует ограничения

если limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) т. е. предел существует и положителен, то f(x) = Ө(g(x))

Общие классы сложности

Обозначение Big-Omega

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

Формальное определение

Пусть f(n) и g(n) - две функции, определенные на множестве положительных вещественных чисел. Запишем f(n) = Ω(g(n)) если существуют положительные константы c и n0 такие, что:

0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .

Заметки

f(n) = Ω(g(n)) означает, что f(n) растет асимптотически не медленнее g(n) . Также можно сказать о Ω(g(n)) когда анализа алгоритма недостаточно для утверждения о Θ(g(n)) или / и O(g(n)) .

Из определений обозначений следует теорема:

Для двух любых функций f(n) и g(n) имеем f(n) = Ө(g(n)) тогда и только тогда, когда f(n) = O(g(n)) and f(n) = Ω(g(n)) .

Графически Ω-обозначение может быть представлено следующим образом:

Например, пусть f(n) = 3n^2 + 5n - 4 . Тогда f(n) = Ω(n^2) . Это также верно f(n) = Ω(n) или даже f(n) = Ω(1) .

Другой пример для решения алгоритма идеального совпадения: если число вершин нечетное, тогда выведите «Нет идеального соответствия», в противном случае попробуйте все возможные сопоставления.

Мы хотели бы сказать, что алгоритм требует экспоненциального времени, но на самом деле вы не можете доказать нижнюю границу Ω(n^2) используя обычное определение Ω поскольку алгоритм работает в линейном времени для n нечетных. Мы должны вместо этого определить f(n)=Ω(g(n)) , сказав для некоторой константы c>0 , f(n)≥ cg(n) для бесконечного числа n . Это дает хорошее соответствие между верхней и нижней границами: f(n)=Ω(g(n)) если f(n) != o(g(n)) .

Рекомендации

Формальное определение и теорема взяты из книги «Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Введение в алгоритмы».

Сравнение асимптотических обозначений

Пусть f(n) и g(n) - две функции, определенные на множестве положительных вещественных чисел, c, c1, c2, n0 - положительные вещественные константы.

нотация	f (n) = O (g (n))	f (n) = Ω (g (n))	f (n) = Θ (g (n))	f (n) = o (g (n))	f (n) = ω (g (n))
Формальное определение	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n)	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n)	∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n)
Аналогия между асимптотическим сравнением f, g и действительных чисел a, b	a ≤ b	a ≥ b	a = b	a < b	a > b
пример	7n + 10 = O(n^2 + n - 9)	n^3 - 34 = Ω(10n^2 - 7n + 1)	1/2 n^2 - 7n = Θ(n^2)	5n^2 = o(n^3)	7n^2 = ω(n)
Графическая интерпретация

Асимптотические обозначения могут быть представлены на диаграмме Венна следующим образом:

связи

Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Введение в алгоритмы.