Priekšnosacījums - Asimptotiskie apzīmējumi , Asimptotisko apzīmējumu īpašības , Algoritmu analīze
1. Lielais O apzīmējums (O):

Tas ir definēts kā augšējā robeža, un algoritma augšējā robeža ir visvairāk nepieciešamais laiks (sliktākā gadījuma veiktspēja).
Lielais O apzīmējums tiek izmantots, lai aprakstītu asimptotiskā augšējā robeža .

Matemātiski, ja f(n) apraksta algoritma darbības laiku; f(n) ir O(g(n)) ja pastāv pozitīva konstante C un n0 tāds, ka,

0 <= f(n) = n0

n = izmanto, lai piešķirtu funkciju augšējai robežai.
Ja funkcija ir O(n) , tas notiek automātiski O(n-kvadrāts) arī.

Grafisks piemērs priekš Lielais O:

kā java izsaukt metodi

2. Lielais Omega apzīmējums (Ω):

Tas tiek definēts kā algoritma apakšējā robeža un apakšējā robeža ir vismazākais nepieciešamais laiks (visefektīvākais iespējamais veids, citiem vārdiem sakot, labākais gadījums).
Tieši kā O apzīmējums nodrošināt an asimptotiskā augšējā robeža , Ak apzīmējums nodrošina asimptotiskā apakšējā robeža .

Ļaujiet f(n) definēt algoritma darbības laiku;
f(n) teikts, ka ir Ω(g(n)) ja pastāv pozitīva konstante C un (n0) tāds, ka

0 <= Cg(n) = n0

hashset vs hashmap

n = izmanto, lai dotu funkcijas apakšējo robežu
Ja funkcija ir Ω (n-kvadrāts) tas ir automātiski Ak(n) arī.

Grafisks piemērs priekš Lielā Omega (Ω):

3. Lielais teta apzīmējums (Θ) :

Tas tiek definēts kā visciešākā saite un visciešākā saite ir labākais no visiem sliktākajiem gadījumiem, ko algoritms var veikt.

Ļaujiet f(n) definēt algoritma darbības laiku.
f(n) teikts, ka ir Θ(g(n)) ja f(n) ir O(g(n)) un f(n) ir Ω(g(n)).

Matemātiski,

0 <= f(n) = n0
0 <= C2g(n) = n0

Apvienojot abus vienādojumus, mēs iegūstam:

javascript base64 atšifrējums

0 <= C2g(n) <= f(n) = n0

Vienādojums vienkārši nozīmē, ka pastāv pozitīvas konstantes C1 un C2 tā, ka f(n) ir starp C2 g(n) un C1g(n).

Grafisks piemērs Big Theta (Θ) :

Atšķirība starp Big Oh, Big Omega un Big Theta:

Lai iegūtu sīkāku informāciju, lūdzu, skatiet: Algoritmu projektēšana un analīze .