|
[quote="mandark"]f(n)<= 5g(n) za n>=No (n sa indexom nula)
**** 4logn + 5 <= 5g(n) <==> logn >= 5 <==> n>=10e5 = 100 000
Dakle treba uzeti No=100 000
zakljucak: slozenost algoritma je O(logn)
Zanima me sto je No (malo n index 0),pojasnjenje relacije ****[/quote]
n_0 je, ajmo tako reci, prvi n od kojeg vrijedi relacija. Slicno kao kod konvergencija nizova. 8)
Relacija **** ti kaze da g(n) ne raste sporije od f(n). :)
[quote="mandark"]i zasto slozenost= logn. :?[/quote]
Vidi, nas zanima "[i]koliko brzo[/i]" raste neka funkcija. :? Znaci, ako ja znam da ce mi algoritam na nekoj odredjenoj masini raditi 10 sekundi za n=17000, mene onda zanima koliko ce raditi za n=34000. Da li duplo dulje, 4 puta dulje i sl. Tu mi je sada totalno svejedno kolika je ona konstanta, jer ona ne utjece na taj podatak, nego samo na konkretno vrijeme izvrsavanja. :)
Eh, sada ostaje vjecni problem za studente: zasto nije bitno tocno vrijeme izvrsavanja? :-k
Zato jer ako ja kupim "duplo brzu" masinu (stogod to znacilo), onda ce se moj program izvrsavati duplo brze. :) Takodjer, ako uzmem drugi compiler (ili cak drugi programski jezik!) vrijeme izvrsavanja ce se promijeniti. :crazyeyes: Ali, [b]ono sto se nece promijeniti[/b] je upravo omjer: duplo veci problem -> koliko [b]puta[/b] dulje izvrsavanje? :) Takodjer, mi ovdje ocjenjujemo [b]algoritme[/b], a ne njihove implementacije izvodjene na odredjenim racunalima :!:
Realno bi bilo racunati broj operacija nekog algoritma, ali to je u praxi gotovo uvijek neizracunljivo, pa uzimamo ovakvu definiciju slozenosti kao nesto sto dovoljno dobro aproximira ono sto zelimo... 8)
Nadam se da je sada donekle jasnije... :)
| mandark (napisa): | f(n)⇐ 5g(n) za n>=No (n sa indexom nula)
**** 4logn + 5 ⇐ 5g(n) ⇔ logn >= 5 ⇔ n>=10e5 = 100 000
Dakle treba uzeti No=100 000
zakljucak: slozenost algoritma je O(logn)
Zanima me sto je No (malo n index 0),pojasnjenje relacije **** |
n_0 je, ajmo tako reci, prvi n od kojeg vrijedi relacija. Slicno kao kod konvergencija nizova. 
Relacija **** ti kaze da g(n) ne raste sporije od f(n). 
| mandark (napisa): | i zasto slozenost= logn.  |
Vidi, nas zanima "koliko brzo" raste neka funkcija. Znaci, ako ja znam da ce mi algoritam na nekoj odredjenoj masini raditi 10 sekundi za n=17000, mene onda zanima koliko ce raditi za n=34000. Da li duplo dulje, 4 puta dulje i sl. Tu mi je sada totalno svejedno kolika je ona konstanta, jer ona ne utjece na taj podatak, nego samo na konkretno vrijeme izvrsavanja.
Eh, sada ostaje vjecni problem za studente: zasto nije bitno tocno vrijeme izvrsavanja? 
Zato jer ako ja kupim "duplo brzu" masinu (stogod to znacilo), onda ce se moj program izvrsavati duplo brze. Takodjer, ako uzmem drugi compiler (ili cak drugi programski jezik!) vrijeme izvrsavanja ce se promijeniti.  Ali, ono sto se nece promijeniti je upravo omjer: duplo veci problem → koliko puta dulje izvrsavanje? Takodjer, mi ovdje ocjenjujemo algoritme, a ne njihove implementacije izvodjene na odredjenim racunalima 
Realno bi bilo racunati broj operacija nekog algoritma, ali to je u praxi gotovo uvijek neizracunljivo, pa uzimamo ovakvu definiciju slozenosti kao nesto sto dovoljno dobro aproximira ono sto zelimo...
Nadam se da je sada donekle jasnije...
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
