Ero sivun ”Asymptoottinen suoritusaika” versioiden välillä
| [katsottu versio] | [katsottu versio] |
Poistettu sisältö Lisätty sisältö
yleisesti tunnettu nimi |
yleisesti tunnetaan iso o notaationa, harvemmin bachmann-landau -notaationa, vielä harvemmin ordo-notaationa.. |
||
Rivi 13:
* ''ω''-notaatio – aidosti {{Lähde|10. kesäkuuta 2009}} alhaalta rajoitettu, joka tarkoittaa lyhyesti '''Suoritukseen kuluu vähintään näin monta alkeisoperaatiota, mutta se voi kuluttaa enemmänkin'''
==
Yleisesti ''iso-O -notaationa'' tunnettu merkintätapa on tunnettu myös Bachmann–Landau -notaationa.
Matemaattinen merkitys:<BR>▼
Myös termiä ''Ordo-notaatio'' käytetään.{{lähde}}
''Ο''(g(n)) = {f(n) | 0 ≤ f(n) ≤ c<sub>2</sub>g(n) kaikilla n ≥ n<sub>0</sub>}<BR>▼
missä c<sub>2</sub> on jokin positiivinen reaaliluku ja n<sub>0</sub> on jokin luonnollinen luku.▼
▲..missä c<sub>2</sub> on jokin positiivinen reaaliluku ja n<sub>0</sub> on jokin luonnollinen luku.
Merkitään, että f(n) = ''Ο''(g(n)).
Rivi 23 ⟶ 26:
Ordo-merkintä kuvastaa pahinta mahdollista tapausta. Se rajoittaa ylhäältä päin aidosti algoritmin suoritusaikaa. Esimerkiksi [[pikalajittelu]] toimii nopeimmin jos alkiot ovat syötteessä mahdollisimman sekaisin. [[Lisäyslajittelu]] toimii nopeimmin jos alkiot ovat jo järjestyksessä, ja hitaimmin jos käänteisessä järjestyksessä. Ordo-notaatiolla jätetään syötteen aiheuttama suoritusajan vaihtelu huomiotta, ja keskitytään vain pahimpaan mahdolliseen tapaukseen, jolloin lajittelu kestää eniten aikaa.
Ordo-notaatiolla siis ilmoitetaan:
:'''Suoritukseen kuluu maksimissaan näin monta alkeisoperaatiota syötteestä riippumatta, mutta se voi valmistua vähemmälläkin'''
== Theta-notaatio ==
Matemaattinen merkitys:
: ''Θ''(g(n)) = {f(n) | 0 ≤ c<sub>1</sub>*g(n) ≤ f(n) ≤ c<sub>2</sub>g(n) kaikilla n ≥ n<sub>0</sub>}
.. missä c<sub>1</sub>,c<sub>2</sub> on jokin positiivinen reaaliluku ja n<sub>0</sub> on jokin luonnollinen luku.
f(n) on jokin ''Θ''(g(n)):ään sisältyvä funktio, toisin sanoen: on olemassa sellaiset vakiot c<sub>1</sub>,c<sub>2</sub> että f(n) on jossain välillä c<sub>1</sub>*g(n)..c<sub>2</sub>*g(n), silloin kun n kasvaa riittävän suureksi.
Rivi 38 ⟶ 41:
Theta-merkintä kertoo sekä hitaimman että nopeimman suoritusajan. Toisin sanoen, algoritmin toimiessa ''Θ''(n<sup>2</sup>) -ajassa, se Ordo-notaation perusteellakin toimii ''Ο''(n<sup>2</sup>) -ajassa. Mutta, jos algoritmi toimii ''Ο''(n<sup>2</sup>) ajassa, siitä ei välittömästi seuraa, että algoritmi toimisi ''Θ''(n<sup>2</sup>) -ajassa, sillä ''Θ''(f(n)) sisältää ''Ο''(f(n)):n mutta ''Ο''(f(n)) ei sisällä ''Θ''(f(n)):aa.
Theta-notaatiolla siis ilmoitetaan:
: '''Tarvittavien alkeisoperaatioiden määrä on aina tällä välillä syötteestä riippumatta'''
== Esimerkki ==
| |||