Вопрос по algorithm – Что именно представляет большая нотация?

155

Я действительно запутался в разнице между нотацией большого О, большой Омеги и большой тэты.

Я понимаю, что большой О - это верхняя граница, а большой Омега - это нижняя граница, но что именно делает большой & # x4E8; (тета) представляют?

Я прочитал, что это значитtight bound, Но что это значит?

Возможный дубликатDifference between lower bound and tight bound? Damjan Pavlica

Ваш Ответ

4   ответа
298

что такое большой О, большая Тета и большая Омега. Они всенаборы функций.

Большой О дает верхасимптотическая границав то время как большая Омега дает нижнюю границу. Большая Тета дает оба.

Все что естьӨ(f(n)) это такжеO(f(n)), но не наоборот.
T(n) Говорят, что вӨ(f(n)) если это как вO(f(n)) И вOmega(f(n)).
В наборах терминологии,Ө(f(n)) is the пересечение изO(f(n)) а такжеOmega(f(n))

Например, сортировка слиянием в худшем случаеO(n*log(n)) а такжеOmega(n*log(n)) - и, таким образом, такжеӨ(n*log(n)), но это такжеO(n^2), посколькуn^2 асимптотически "больше" чем это. Тем не менее, этоnot Ө(n^2), Так как алгоритм неOmega(n^2).

A bit deeper mathematic explanation

O(n) асимптотическая верхняя граница. ЕслиT(n) являетсяO(f(n)), это означает, что из определенногоn0есть константаC такой, чтоT(n) <= C * f(n), С другой стороны, Биг Омега говорит, что существует постояннаяC2 такой, чтоT(n) >= C2 * f(n))).

Do not confuse!

Не путать с анализом наихудших, лучших и средних случаев: все три (Omega, O, Theta) обозначенияnot связанных с лучшим, худшим и средним случаями анализа алгоритмов. Каждый из них может быть применен к каждому анализу.

We usually use it to analyze complexity of algorithms (как пример сортировки слиянием выше). Когда мы говорим «Алгоритм А являетсяO(f(n))"что мы на самом деле имеем в виду" - сложность алгоритмов в худшем1 анализ случаяO(f(n))& Quot; - значение - оно масштабируется "аналогично" (или формально, не хуже чем) функцияf(n).

Why we care for the asymptotic bound of an algorithm?

Ну, есть много причин для этого, но я считаю, что наиболее важными из них являются:

It is much harder to determine the exact complexity function, thus we "compromise" on the big-O/big-Theta notations, which are informative enough theoretically. The exact number of ops is also platform dependent. For example, if we have a vector (list) of 16 numbers. How much ops will it take? The answer is: it depends. Some CPUs allow vector additions, while other don't, so the answer varies between different implementations and different machines, which is an undesired property. The big-O notation however is much more constant between machines and implementations.

Чтобы продемонстрировать эту проблему, взгляните на следующие графики: enter image description here

Ясно, чтоf(n) = 2*n "хуже" чемf(n) = n, Но отличие не так сильно, как от другой функции. Мы это видимf(n)=logn быстро становится намного ниже, чем другие функции, иf(n) = n^2 быстро становится намного выше, чем другие.
Таким образом, по указанным выше причинам мы "игнорируем" постоянные множители (2 * в примере с графиками) и принимают только обозначение big-O.

В приведенном выше примереf(n)=n, f(n)=2*n оба будут вO(n) И вOmega(n) - и, таким образом, также будет вTheta(n).
С другой стороны -f(n)=logn будет вO(n) (это «лучше», чемf(n)=n), но НЕ будет вOmega(n) - и, следовательно, также не будет вTheta(n).
симметрично,f(n)=n^2 будет вOmega(n), но НЕ вO(n), а значит - тоже НЕTheta(n).

1Обычно, хотя и не всегда. когда класс анализа (худший, средний и лучший) отсутствует, мы действительно имеем в видуthe worst case.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededupperError: User Rate Limit ExceedednError: User Rate Limit ExceededlowerError: User Rate Limit ExceedednError: User Rate Limit Exceededupper and lowerError: User Rate Limit ExceedednError: User Rate Limit ExceedednError: User Rate Limit ExceedednError: User Rate Limit Exceededn0Error: User Rate Limit ExceedednError: User Rate Limit Exceededn0Error: User Rate Limit Exceededn0Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededf(n) = n^2Error: User Rate Limit ExceedednError: User Rate Limit ExceedednError: User Rate Limit Exceededc*nError: User Rate Limit ExceedednError: User Rate Limit Exceeded
1
Big Theta notation:

Если у нас есть функции с положительными значениями f (n) и g (n) принимает аргумент с положительными значениями n, то & # x3F4; (g (n)) определяется как {f (n): существуют константы c1, c2 и n1 для все n & gt; = n1}

где c1 g (n) = f (n) = c2 g (n)

Let's take an example:

пусть f (n) =

г (п) =

с1 = 5 и с2 = 8 и n1 = 1

Среди всех обозначений & # x3F4; нотация дает лучшую интуицию о скорости роста функции, потому что она дает нам жесткую границу в отличие от больших-ой и больших -омега который дает верхнюю и нижнюю границы соответственно.

& # X3F4; говорит нам, что g (n) максимально приближена к f (n), скорость роста g (n) максимально приближена к скорости роста f (n).

see the image to get a better intuition

84

что в данной функции алгоритм является как big-O, так и big-Omega.

Например, если этоӨ(n)то есть некоторая постояннаяkтак, что ваша функция (во время выполнения, что угодно), больше, чемn*k для достаточно большогоnи некоторая другая константаK так что ваша функция меньшеn*K для достаточно большогоn.

Другими словами, для достаточно большогоn, он зажат между двумя линейными функциями:

Заk < K а такжеn достаточно большой,n*k < f(n) < n*K

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
13

Theta(n): Функцияf(n) принадлежитTheta(g(n)), если существуют положительные постоянныеc1 а такжеc2 такой, чтоf(n) может быть зажат междуc1(g(n)) а такжеc2(g(n)), то есть он дает как верхнюю, так и нижнюю границу.

Theta(g(n)) = { f(n) : there exists positive constants c1,c2 and n1 such that 0<=c1(g(n))<=f(n)<=c2(g(n)) for all n>=n1 }

когда мы говоримf(n)=c2(g(n)) или жеf(n)=c1(g(n)) он представляет асимптотически тесную границу.

O(n): Это дает только верхнюю границу (может быть или не быть жестким)

O(g(n)) = { f(n) : there exists positive constants c and n1 such that 0<=f(n)<=cg(n) for all n>=n1}

ex: Связанный2*(n^2) = O(n^2) асимптотически туго, в то время как предел2*n = O(n^2) не асимптотически туго.

o(n): Это дает только верхнюю границу (никогда не жесткую границу)

the notable difference between O(n) & o(n) is f(n) is less than cg(n) for all n>=n1 but not equal as in O(n).

ex: 2*n = o(n^2), но2*(n^2) != o(n^2)

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы