Časovna zahtevnost

Iz MaFiRaWiki

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