Wat betekent de grote Ө-notatie precies?

Ik ben echt in de war over de verschillen tussen grote O, grote Omega en grote Theta-notatie.

Ik begrijp dat grote O de bovengrens is en grote Omega de ondergrens, maar wat stelt grote Ө (theta) precies voor?

Ik heb gelezen dat het strak gebondenbetekent, maar wat betekent dat?

Antwoord 1, autoriteit 100%

Het betekent dat het algoritme zowel big-O als big-Omega is in de gegeven functie.

Als het bijvoorbeeld Ө(n)is, dan is er een constante K, zodat uw functie (runtime, wat dan ook) groter is dan n*Kvoor voldoende grote n, en een andere constante Kzodat uw functie kleiner is dan n*Kvoor voldoende grote n.

Met andere woorden, voor voldoende grote nis het ingeklemd tussen twee lineaire functies:

Voor k < Ken nvoldoende groot, n*k < f(n) < n*K

Antwoord 2, autoriteit 94%

Laten we eerst eens begrijpen wat grote O, grote Theta en grote Omega zijn. Het zijn allemaal setsvan functies.

Grote O geeft bovengrens asymptotische grens, terwijl grote Omega een ondergrens geeft. Big Theta geeft beide.

Alles wat Ө(f(n))is, is ook O(f(n)), maar niet andersom.

T(n)staat in Ө(f(n))als het beide in O(f(n))en in Omega(f(n)).
In de terminologie van sets is Ө(f(n))de kruispuntvan O(f(n))en Omega(f(n))

Bijvoorbeeld, merge sort worst case is zowel O(n*log(n))als Omega(n*log(n))– en is dus ook Ө(n*log(n)), maar het is ook O(n^2), aangezien n^2asymptotisch “groter is ” dan het. Het is echter nietӨ(n^2), aangezien het algoritme niet Omega(n^2)is.

Een wat diepere wiskundige uitleg

O(n)is een asymptotische bovengrens. Als T(n)O(f(n))is, betekent dit dat er vanaf een bepaalde n0een constante Czodanig dat T(n) <= C * f(n). Aan de andere kant zegt big-Omega dat er een constante c2is zodat T(n) >= C2 * f(n))).

Niet verwarren!

Niet te verwarren met analyse van slechtste, beste en gemiddelde gevallen: alle drie de notaties (Omega, O, Theta) zijn nietgerelateerd aan de analyse van beste, slechtste en gemiddelde gevallen van algoritmen. Elk van deze kan op elke analyse worden toegepast.

We gebruiken het meestal om de complexiteit van algoritmen te analyseren(zoals het bovenstaande voorbeeld van samenvoegen). Als we zeggen “Algoritme A is O(f(n))“, bedoelen we eigenlijk “De complexiteit van de algoritmen onder de slechtste¹-analyse is O(f(n))” – wat betekent – het schaalt “vergelijkbaar” (of formeel, niet slechter dan) de functie f(n).

Waarom geven we om de asymptotische grens van een algoritme?

Nou, er zijn veel redenen voor, maar ik denk dat de belangrijkste zijn:

1. Het is veel moeilijker om de exactecomplexiteitsfunctie te bepalen, dus “compromis” we met de big-O/big-Theta-notaties, die theoretisch informatief genoeg zijn.
2. Het exacte aantal ops is ook platformafhankelijk. Als we bijvoorbeeld een vector (lijst) van 16 getallen hebben. Hoeveel operaties zal het kosten? Het antwoord is: het hangt ervan af. Sommige CPU’s laten vectortoevoegingen toe, terwijl andere dat niet doen, dus het antwoord varieert tussen verschillende implementaties en verschillende machines, wat een ongewenste eigenschap is. De big-O-notatie is echter veel constanter tussen machines en implementaties.

Bekijk de volgende grafieken om dit probleem te demonstreren:

Het is duidelijk dat f(n) = 2*n“slechter” is dan f(n) = n. Maar het verschil is niet zo drastisch als bij de andere functie. We kunnen zien dat f(n)=lognsnel veel lager wordt dan de andere functies, en f(n) = n^2snel veel hoger wordt dan de andere .

Dus – vanwege de bovenstaande redenen “negeren” we de constante factoren (2* in het voorbeeld van een grafiek) en nemen we alleen de grote O-notatie.

In het bovenstaande voorbeeld zullen f(n)=n, f(n)=2*nzowel in O(n)als in Omega(n)– en zal dus ook in Theta(n)staan.

Aan de andere kant – f(n)=lognzal in O(n)staan (het is “beter” dan f(n)=n), maar zal NIET in Omega(n)staan – en dus ook NIET in Theta(n).

Symetrisch, zal f(n)=n^2in Omega(n)staan, maar NIET in O(n), en dus – is ook NIET Theta(n).

¹Meestal, maar niet altijd. wanneer de analyseklasse (slechtste, gemiddelde en beste) ontbreekt, bedoelen we echt het slechtste geval.

Antwoord 3, autoriteit 14%

Theta(n):Een functie f(n)hoort bij Theta(g(n)), als er positieve constanten zijn c1en c2zodat f(n)kan worden ingeklemd tussen c1(g(n))en c2(g(n)). d.w.z. het geeft zowel boven- als ondergrens.

Theta(g(n)) = { f(n) : er bestaan positieve constanten c1,c2 en n1 zodat
0<=c1(g(n))<=f(n)<=c2(g(n)) voor alle n>=n1 }

wanneer we zeggen f(n)=c2(g(n))of f(n)=c1(g(n))staat dit voor asymptotisch strak gebonden .

O(n):Het geeft alleen de bovengrens (al dan niet strak)

O(g(n)) = { f(n) : er bestaan positieve constanten c en n1 zodat 0<=f(n)<=cg(n) voor alle n>=n1}

ex: De gebonden 2*(n^2) = O(n^2)is asymptotisch strak, terwijl de gebonden 2*n = o(n^2)is niet asymptotisch strak.

o(n):Het geeft alleen een bovengrens (nooit een strakke grens)

het opmerkelijke verschil tussen O(n) & o(n) is f(n) is kleiner dan cg(n)
voor alle n>=n1 maar niet gelijk aan O(n).

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

Antwoord 4, autoriteit 5%

Ik hoop dat dit is wat je misschien wilt vinden in de klassieke CLRS(pagina 66):

Antwoord 5

Grote Theta-notatie:

Niets om in de war te brengen vriend!!

Als we een functie met een positieve waarde f(n) hebben en g(n) een argument met een positieve waarde n neemt, dan is ϴ(g(n)) gedefinieerd als {f(n): er bestaan constanten c1,c2 en n1 voor alle n>=n1}

waarbij c1 g(n)<=f(n)<=c2 g(n)

Laten we een voorbeeld nemen:

let f(n)=

g(n)=

c1=5 en c2=8 en n1=1

Van alle notaties geeft notatie de beste intuïtie over de groeisnelheid van de functie, omdat het ons een strakke grens geeft in tegenstelling tot big-oh en big-omega
die respectievelijk de boven- en ondergrenzen geeft.

ϴ vertelt ons dat g(n) zo dicht mogelijk bij f(n) ligt, de groeisnelheid van g(n) zo dicht mogelijk bij de groeisnelheid van f(n) ligt.

Antwoord 6

Allereerst theorie

1. Grote O = Bovengrens O(n)

2. Theta = Orderfunctie – theta(n)

3. Omega = Q-notatie (ondergrens) Q(n)

Waarom zijn mensen zo in de war?

In veel Blogs & Boeken Hoe deze verklaring wordt benadrukt, is als

“Dit is Big O(n^3)” enz.

en mensen verwarren vaak zoals het weer

O(n) == theta(n) == Q(n)

Maar wat de moeite waard is om in gedachten te houden is het zijn gewoon wiskundige functies met namen O, Theta & Omega

dus ze hebben dezelfde algemene formule van polynoom,

Laat,

f(n) = 2n4 + 100n2 + 10n + 50 dan,

g(n) = n4, dus g(n) is een functie die de functie als invoer neemt en variabele teruggeeft met het grootste vermogen,

Dezelfde f(n) & g(n) voor Hieronder alle uitleg

Grote O – Functie (biedt bovengrens)

Grote O(n4) = 3n4, omdat 3n4 > 2n4

3n4 is de waarde van Big O(n4) Net als f(x) = 3x

n4speelt hier een rol van xdus,

N4 vervangen door x’so, Big O(x’) = 2x’, nu zijn we allebei blij dat het algemene concept is

Dus 0 ≤ f(n) ≤ O(x’)

O(x’) = cg(n) = 3n4

Waarde,

0 ≤ 2n4 + 100n2 + 10n + 50 ≤ 3n4

3n4 is onze bovengrens

Theta(n) biedt ondergrens

Theta(n4) = cg(n) = 2n4 Omdat 2n4 ≤ Ons voorbeeld f(n)

2n4 is de waarde van Theta(n4)

dus, 0 ≤ cg(n) ≤ f(n)

0 ≤ 2n4 ≤ 2n4 + 100n2 + 10n + 50

2n4 is onze ondergrens

Omega n – Bestelfunctie

Dit wordt berekend om erachter te komen dat de ondergrens van het weer vergelijkbaar is met de bovengrens,

Geval 1). Bovengrens is vergelijkbaar met ondergrens

if Upper Bound is Similar to Lower Bound, The Average Case is Similar
Example, 2n4 ≤ f(x) ≤ 2n4,
Then Omega(n) = 2n4

Geval 2). als bovengrens niet gelijk is aan ondergrens

in this case, Omega(n) is Not fixed but Omega(n) is the set of functions with the same order of growth as g(n).
Example 2n4 ≤ f(x) ≤ 3n4, This is Our Default Case,
Then, Omega(n) = c'n4, is a set of functions with 2 ≤ c' ≤ 3

Hoop dat dit wordt uitgelegd!!