Если функция Θ (f (n)), это означает, что она является одновременно O (f (n)) и Ω (f (n))
Обратное также верно, если функцияравно O (f (n)) и Ω (f (n)), тогда оно равно Θ (f (n))
. Доказательство этого простое:
g(n)=Θ(f(n)) => exists n0, c1 and c2 such that: c1f(n)<g(n)<c2f(n) for n>n0
Возьмем только первую половину:
exists n0 and c1 such that: c1f(n)<g(n) for n>n0 => g(n)=Ω(f(n))
А вторую половину:
exists n0 and c2 such that: g(n)<c2f(n) for n>n0 => g(n)=O(f(n))
Доказательство обратное аналогично.
Редактировать: Немного света о том, что означают Θ, O и Ω.
Вы, наверное, уже видели определения Θ, O и Ω (если нет, я только что упомянул все три из них в приведенном выше доказательстве).
Итак, помимо их математического определения, что они означают?
В основном, думайте о них так:
g(n) = O(f(n)) Это означает, что когда n становится большимf(n) всегда имеет большее значение, чем g(n).ну, если быть более точным, то не f(n), а его постоянное кратное.Например, n+100 - это O(n^2), потому что для n>10, 1*n^2>n+100.Также для n>3, 11*n^2>n+100. С учетом всех этих обозначений константа не играет важной роли, так как именно f(n) определяет, как функция растет .Обратите внимание, что запись O показывает верхнюю границу функции и поэтому не является уникальной.Например, если f(n)=O(n), то это также O(n^2) и O(nlogn) и т. Д., Но (возможно) не O(sqrt(n))g(n) = Ω(f(n)) Это в точности обратное значение O. Следовательно,это показывает, что f(n) является нижней границей для g(n) (снова умноженной на постоянный коэффициент), и снова, это не уникально.Например, если f(n)=Ω(n), то это также Ω(1) и Ω(1/n).У вас всегда есть
g(n) = Ω(f(n)) <=> f(n) = O(g(n))
g(n) = Θ((f(n)) Это жесткая граница для роста вашей функции.В основном это означает, что g(n) имеет такой же рост, как и f(n), хотя это может быть не так гладко, как f(n).Это не является гладким, так как f(n) - прелесть того, что делает Θ: у вас есть алгоритм с временем выполнения, которое не просто выражается, но с помощью Θ вы можете его проанализировать.g(n) = Θ((f(n)) выглядит примерно так:
| ---- 2*f(n)
| / /\ ---(g(n)
| ---- / \/ -------- f(n)
| / / /
| ---- /\ / --------
| / ----- \/ /
| ---- / --------
| / / /
| ---- --------
|/ /
+---------------------------------------------
Забавные факты:
f(n) = O(f(n)), потому что у вас есть для всех n, 2*f(n)>f(n) (Пример 2, любая константа больше 1 - это хорошо).Наименьшая верхняя граница функции - это сама функция! - Аналогично,
f(n) = Ω(f(n)) и f(n) = Θ(f(n)).Кроме того, самой большой нижней границей функции является сама функция. - Θ показывает точный рост функции, и если вы найдете ее для своего алгоритма, то это лучшее описание.Тем не менее, многие алгоритмы имеют сложное поведение или в лучшем случае имеют разный рост в зависимости от их входных данных (например, сортировка вставки
Θ(n) при отсортированном вводе и Θ(n^2) при обратно отсортированном вводе) Следовательно, поиск finding алгоритмане всегда возможно. - O показывает верхнюю границу выполнения функции.Обычно это то, что люди вычисляют для своих алгоритмов.Делая это, говорят они, несмотря ни на что, мой алгоритм не хуже этого, но в некоторых случаях он может быть лучше.Например, сортировка вставки:
O(n^2). - Иногда O не показывает наилучшую (минимальную) верхнюю границу, потому что найти это просто слишком сложно.В этих случаях О все еще приходит на помощь.Например, если у вас есть алгоритм, который работает с входными данными размера 1000 в приложении пользовательского интерфейса (допустим, задержка, скажем, 0,5 с), то если ваш алгоритм равен
O(n^2), то это хорошо, хотя выполнение худшего случаяалгоритм на самом деле ниже, чем это (но вам было слишком сложно его найти).Лучшая верхняя граница - это скорость роста алгоритма в худшем случае.В примере сортировки вставкой наихудший вариант выполнения равен Θ(n^2), и поэтому наилучшая верхняя граница, которую вы можете дать алгоритму, равна O(n^2) (в отличие от O(n^3), например). - Ω это нне очень полезно на практике, вы никогда не хотите сказать, что мой алгоритм в лучшем случае такой, но может быть и хуже (это плохая реклама)!Однако в информатике это очень полезно.В большинстве случаев, чтобы доказать, что что-то не может быть сделано лучше.Например, если в
Θ(n^3) есть алгоритм, решающий проблему, и вы докажете, что любой алгоритм, решающий проблему, должен быть Ω(n^3), то это означает, что никогда не будет лучшего алгоритма, чем тот, который у вас уже есть (таквы как бы говорите остальным не ищите, вы не найдете его )
Существует множество математик O-обозначений, которые нетруднопонять или изобрести себя.Вот некоторые примеры:
- O (f (n) + g (n)) = O (max (f (n), g (n)))
- O (f(n)) + O (g (n)) = O (f (n) + g (n))
- O (f (n)) O (g (n)) = O (f (n) g (n))
- O (cf (n)) = O (f (n)), где c - постоянная
Большинство из них можно доказать немедленно,поместив их в определение обозначения О.
Первое из этих правил, пожалуй, самое полезное.Если ваш алгоритм состоит из двух разделов, один из которых устанавливает некоторый массив размером n в ноль, а затем делает что-то из O(nlogn), тогда общий порядок равен O(n+nlogn), который просто равен O(nlogn).
Это означает, чтоматематически говоря, лучше иметь тысячу O(nlogn) предварительной обработки и алгоритм O(nlogn) решения проблемы, чем иметь краткий алгоритм O(n^1.5).Обратите внимание, что на практике это не обязательно лучше.Почему ты спрашиваешь?Первый - O(nlogn), а второй - O(n^1.5), так что первый лучше сказать?Хорошо помните, что запись O показывает поведение функции асимптотически .Это означает, что да, если ваш вывод становится очень-очень-очень большим, первый алгоритм (с тысячью предварительных процессов) будет лучше, но в практическом диапазоне ваш n, 1000nlogn может быть намного больше, чем n^1.5.