Hoe big-theta te berekenen

Kan iemand me een realtime voorbeeld geven voor het berekenen van grote theta.

Is grote theta zoiets als een gemiddeld geval, (min-max)/2?

Ik bedoel (minimale tijd – grote O)/2

Corrigeer me als ik het mis heb, bedankt

Antwoord 1, autoriteit 100%

Big-theta-notatie vertegenwoordigt de volgende regel:

Voor elke twee functies f(n), g(n), als f(n)/g(n)en g(n)/f(n)zijn beide begrensd als ntot oneindig groeit, dan f = Θ(g)en g = Θ(f). In dat geval is gzowel een bovengrens als een ondergrens voor de groei van f.

Hier is een voorbeeldalgoritme:

def find-minimum(List) 
  min = +∞
  foreach value in List 
    min = value if min > value
  return min

We willen de kostenfunctie c(n)evalueren, waarbij nde grootte van de invoerlijst is. Dit algoritme voert één vergelijking uit voor elk item in de lijst, dus c(n) = n.

c(n)/n = 1die begrensd blijft als nnaar oneindig gaat, dus c(n)groeit niet sneller dan n. Dit wordt bedoeld met de big-O-notatie c(n) = O(n). Omgekeerd blijft n/C(n) = 1ook begrensd, dus c(n)groeit niet langzamer dan n. Omdat het niet langzamer of sneller groeit, moet het met dezelfde snelheid groeien. Dit wordt bedoeld met theta-notatie c(n) = Θ(n).

Merk op dat c(n)/n²ook begrensd is, dus c(n) = O(n²)ook — big-O-notatie is slechts een bovenste gebonden aan de complexiteit, dus elke O(n)functie is ookO(n²), O(n³)…

Aangezien n²/c(n) = nis niet begrensd, dan c(n) ≠ Θ(n²). Dit is de interessante eigenschap van big-theta notatie: het is zowel een bovengrens en een ondergrens van de complexiteit.

Antwoord 2, Autoriteit 17%

Big theta is een strak gebonden, een functie T(n): if Omega(f(n))<=T(n)<=O(f(n))en Theta (f (n)) is de krappe weg naar T (n).

Met andere woorden Theta (f (n)) beschrijft ‘een functie T (n), indien beide O [grote O] en Omega, ‘beschrijven’ dezelfde T, met hetzelfde f.

b.v. een quicksort [correcte keuzes mediane], neemt altijd maximaal O (nlogn), aan ten minste Omega (nlogn), zodat quicksort [goede keuzes mediane] is Theta (nlogn)

EDIT:
toegevoegd discussie in de reacties:

Het zoeken van een array is nog steeds Theta (n). de Theta-functie geeft niet aan worst / beste geval, maar het gedrag van de gewenste zaak. d.w.z. het zoeken naar een reeks, T (n) = aantal ops voor worst case. hier, uiteraard T(n)<=O(n), maar ook T(n)>=n/2, want in het ergste geval moet je herhalen de gehele array, zodat T(n)>=Omega(n)en dus Theta (n) is asymptotische gebonden

.

Antwoord 3

Van http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations leren we dat “Big O” geeft een bovengrens, terwijl “Big Theta” geeft een boven- en ondergrens, dat wil zeggen in de limiet nnaar oneindig:

f(n) = O(g(n))      -->    |f(n)| < k.g(n)
f(n) = Theta(g(n))  -->    k1.g(n) < f(n) < k2.g(n)

Zo kun je niet afleiden Big Theta van Big O.