C++, časovna zahtevnost

Funkcija MinMax1 v polju a določi indeks, na katerem se nahajata najmanjši in največji element.

Tole je samo vsebinki opis, kaj funkciji delata.

Aktivna operacija naj bo število primerjav.

Torej, gledamo samo primerjave, vse ostale operacije ignoriramo.

Določi število aktivnih operacij pri dani vrednosti n.

Vrednost n pomeni velikost vhodnega polja. Število primerjav moramo podati kot funkcijo tega n-ja.

Funkcija MinMax2 predstavlja alternativo funkciji MinMax1, saj opravi isto nalogo. Določi število aktivnih operacij v najboljšem in najslabšem primeru.

V funkciji MinMax1 se primerjave izvajajo le v zanki, v vsakem ciklu točno dvkrat. Zanka se izvede n-krat, torej funkcija izvede 2n primerjav. Vedno, v najboljšem in najslabšem primeru, je časovna zahtevnost tako O(2n). Enaka je tudi povprečna zahtevnost.

V funkciji MinMax2 se primerjave izvajajo prav tako le v zanki, vendar ne vedno enako mnogokrat v enem ciklu. Lahko se izvede le ena primerjava, če je rezultat true, ali pa dve, kadar je rezultat prve primerjave false. V najboljšem primeru bo rezultat prve primerjave vedno true in se bo tako v vsakem ciklu izvedla le enkrat. V najboljšem primeru imaš tako n primerjav oz zahtevno O(n).
V najslabšem primeru bo pa rezultat prve primerjave vedno false in boš imel po dve primerjavi na cikel oziroma časovno zahtevnost O(2n).
Zdej je treba stuhtat le še, kakšno je povprečno število primerjav oz. kolikokrat v povprečju bo rezultat prve primerjave true? Bi reku da je to 1/2, torej imaš v 1/2 primerov 1 primerjavo, v 1/2 pa 2, v povprečju torej 3/2 na izvedbo zanke. V povprečju je časovna zahtevnost O(1.5n).

ker se konstantni faktor lahko izpusti.

Tole se dogaja, ker vedno lahko postaviš tak dovolj velik N, da hitreje naraščajoča funkcija kljub manjši konstanti "prehiti" počasneje naraščajočo z večjo konstanto.
Če maš pa dve funkciji, ki sta obe O(n) je pa konstanta zanimiva - pomeni konstantno razliko med njima.

Razlika med teorijo in prakso - ko optimiziram algoritem, me konstanta pohitritev vseeno zanima.

Mal se mi zdi smešno, ker je to domača naloga, ki ubistvu ni nič zahtevna ali ne razumljiva. Itak ti piše v skripti/pdf, kak se to beleži, tam je ene 5 primerov različnih, vse je narisano pa še rešeno zravn.


Lp