Časovna zahtevnost

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 17:33, 29 januar 2008
TomazPisanski (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
MatijaLokar (Pogovor | prispevki)

Vrstica 1: Vrstica 1:
{{V delu}} {{V delu}}
-'''Časovna zahtevnost''' T(I) je število računskih korakov, ki jih potrebuje [[program]] ali [[algoritem]] pri danih vhodnih podatkih I, da izračuna rezultat. Računske korake merimo v osnovnih operacijah [[stroj]]a, ki program izvaja, v nekaterih primerih pa tudi bolj abstraktno (na primer, štejemo samo aritmetične operacije in primerjave).+'''Časovna zahtevnost''' T(I) je število računskih korakov, ki jih potrebuje [[program]] ali [[algoritem]] pri danih vhodnih podatkih I, da izračuna rezultat. Računske korake (operacije) merimo v osnovnih opravilih, ki je je sposoben izvesti tisti, ki program izvaja (npr. računalnik), v nekaterih primerih pa tudi bolj abstraktno (na primer, štejemo samo aritmetične operacije in primerjave).
-Poznamo tri vrste časovne zahtevnosti za izbrano obsežnost |I| vhodnih podatkov I - ena nam pove, koliko bo program porabil pri povprečnih podatkih, druga , koliko bo porabil v primeru, da bodo podatki kar najbolj hudobni (worst-case): T<sub>max</sub>(n) = max{T(I); |I| = n}. Spet tretja pa je časovna zahtevnost v najbolj ugodnem primeru, ko so podatki, kar se da 'pohlevni'. T<sub>min</sub>(n) = min{T(I); |I| = n}+Poznamo tri vrste časovne zahtevnosti za izbrano obsežnost |I| vhodnih podatkov I:
 +* povprečno - koliko korakov bo program porabil pri "običajnih" (povprečnih) podatkih,
 +* v naslabšem primeru (worst-case)- koliko bo porabil v primeru, da bodo podatki kar najbolj "hudobni": T<sub>max</sub>(n) = max{T(I); |I| = n}.
 +* v najbolj ugodnem primeru - ko so podatki, kar se da "pohlevni": T<sub>min</sub>(n) = min{T(I); |I| = n}
-Primer: Program potrebuje za urejanje po velikosti n števil, 10 * n * log n operacij v povprečju, n * log n + 5 v najboljšem in n<sup>2</sup>/2 + n v najslabšem primeru. Pišemo, da povprečno porabi O(n log n) operacij, v najboljšem primeru O(n log n) operacij in O(n<sup>2</sup>) v najslabšem primeru (vedno se vpiše le vodilni člen). Nekaj o O notaciji glej na [[Notacija O]]+Časovno zahtevnost običajno izražamo v [[Notacija O | O notaciji]]
-Po hitrosti urejenih nekaj primerov:+Primer: Algoritem potrebuje za urejanje n števil po velikosti v povprečju 10 * n * log n operacij , n * log n + 5 v najboljšem in n<sup>2</sup>/2 + n v najslabšem primeru. Pišemo, da povprečno porabi O(n log n) operacij, v najboljšem primeru O(n log n) operacij in O(n<sup>2</sup>) v najslabšem primeru (vedno se vpiše le vodilni člen).
 + 
 +Nekaj primerov časovnih zahtevnosti:
* O(1) - konstantna zahtevnost - hitrost ni odvisna od obsežnosti vhodnih podatkov * O(1) - konstantna zahtevnost - hitrost ni odvisna od obsežnosti vhodnih podatkov

Trenutna različica

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Časovna zahtevnost T(I) je število računskih korakov, ki jih potrebuje program ali algoritem pri danih vhodnih podatkih I, da izračuna rezultat. Računske korake (operacije) merimo v osnovnih opravilih, ki je je sposoben izvesti tisti, ki program izvaja (npr. računalnik), v nekaterih primerih pa tudi bolj abstraktno (na primer, štejemo samo aritmetične operacije in primerjave).

Poznamo tri vrste časovne zahtevnosti za izbrano obsežnost |I| vhodnih podatkov I:

  • povprečno - koliko korakov bo program porabil pri "običajnih" (povprečnih) podatkih,
  • v naslabšem primeru (worst-case)- koliko bo porabil v primeru, da bodo podatki kar najbolj "hudobni": Tmax(n) = max{T(I); |I| = n}.
  • v najbolj ugodnem primeru - ko so podatki, kar se da "pohlevni": Tmin(n) = min{T(I); |I| = n}

Časovno zahtevnost običajno izražamo v O notaciji

Primer: Algoritem potrebuje za urejanje n števil po velikosti v povprečju 10 * n * log n operacij , n * log n + 5 v najboljšem in n2/2 + n v najslabšem primeru. Pišemo, da povprečno porabi O(n log n) operacij, v najboljšem primeru O(n log n) operacij in O(n2) v najslabšem primeru (vedno se vpiše le vodilni člen).

Nekaj primerov časovnih zahtevnosti:

  • O(1) - konstantna zahtevnost - hitrost ni odvisna od obsežnosti vhodnih podatkov
  • O(log n) - logaritemska zahtevnost
  • O(n) - linearna zahtevnost
  • O(n log n) - zgled za subkvadratno zahtevnost (narašča hitreje kot linearna, počasneje od * kvadratne)
  • O(n2) - kvadratna zahevnost
  • O(nc) - polinomska zahtevnost - kjer je c konstanta
  • O(elog n) - zgled za subeksponentno (vmesno) zahtevnost - (narašča hitreje kot katerikoli polinom in počasneje kot eksponentna.)
  • O(en) - eksponentna zahtevnost
Opomba: Tu razumemo oznako O v smislu Θ, primerjaj članek v Wikipediji.

Glej tudi

Osebna orodja