» »

C++, časovna zahtevnost

C++, časovna zahtevnost

wicked00 ::

Zdravo!
Mene zanima, če bi vedo kdo to naredit...men se tale snov niti malo ne sanja :|....
Naloga:
Funkcija MinMax1 v polju a določi indeks, na katerem se nahajata najmanjši in največji element. Aktivna operacija naj bo število primerjav. Določi število aktivnih operacij pri dani vrednosti n. Funkcija MinMax2 predstavlja alternativo funkciji MinMax1, saj opravi isto nalogo. Določi število aktivnih operacij v najboljšem in najslabšem primeru. Kakšna je povprečna časovna zahtevnost funkcije po metodi štetja aktivnih operacij?

template < class T >
bool MinMax1 (T a[], int n, int& iMin, int& iMax)
{
if (n < 1) return false;
iMin = iMax = 0;
for (int i = 1; i < n; i++)
{
if(a[iMin] > a[i]) iMin = i;
if(a[iMax] < a[i]) iMax = i;
}
return true;
};
-------------------------------------------

template < class T >
bool MinMax1 (T a[], int n, int& iMin, int& iMax)
{
if (n < 1) return false;
iMin = iMax = 0;
for (int i = 1; i < n; i++)
{
if(a[iMin] > a[i]) iMin = i;
else if(a[iMax] < a[i]) iMax = i;
}
return true;
};

hvala vnaprej
LP

WarpedGone ::

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).
Zbogom in hvala za vse ribe

fiction ::

O(2n), O(1.5n) je se zmeraj O(n), ker se konstantni faktor lahko izpusti. Tudi O(n + 42) je O(n).
Intuitivno je, da moras za to, da najdes najvecji ali najmanjsi element, videti vse elemente, kar pomeni linearno casovno zahtevnost. To je v najslabsem, najboljsem ali pa povprecnem primeru. V bistvu je naloga precej neumna, ker gre za isti algoritem, samo da enkrat naredis eno brezvezno primerjavo, ki ti je ne bi bilo treba.

WarpedGone ::

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.
Zbogom in hvala za vse ribe

fiction ::

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.
Jasno, ti gledas kako se obnasa zadeva, ko gre n proti neskocnosti.

Če maš pa dve funkciji, ki sta obe O(n) je pa konstanta zanimiva - pomeni konstantno razliko med njima.
Konstanta je zanimiva tudi, ce imas nek algoritem, ki ima manjso asimptoticno casovno zahtevnost.
Ala O(1000logn) proti O(5n). Ce imas recimo malo elementov (majhen n) se ti mogoce vseeno bolj splaca uporabiti v
splosnem pocasnejsi algoritem (ker bo za tebe vseeno hitrejsi).

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

Ce govoris o praksi, ne bos uporabljal O() notacije. Reces "tole sem pa za 2x pohitril", ne pa "casovna zahtevnost je zdaj O(n/2)". :)

ERGY ::

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


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Se malo fizike...

Oddelek: Šola
136392 (6200) ddeben
»

Išče se hiter algoritem za izračun ene čudne matrične operacije.

Oddelek: Znanost in tehnologija
171987 (1478) Thomas
»

Telekomu za vzgled

Oddelek: Novice / Omrežja / internet
121960 (1960) Boeing
»

Kaznovanje hroščatosti?

Oddelek: Novice / Varnost
181591 (1591) minmax
»

Plug'n'Politix

Oddelek: Novice / --Nerazporejeno--
61703 (1703) trillian

Več podobnih tem