[quote="maja"]jel mi moze neko rec kolka je slozenost algoritma binarno pretrazivanje[/quote]
Onako napamet... Ako imas n=2^k elemenata liste...
Prvo pregledavas niz duljine 2^k tako da provjeris onog u sredini, tj. sa indexom 2^{k-1}.
Ako nisi nasla element, pretrazujes niz (lijevi ili desni) duljine 2^{k-1}.
I tako u svakom koraku skratis niz na pola. Dakle, najveci broj koraka (tj. dijeljenja pocetnog n sa 2) je k = log_2 n.
Drugim rijecima, slozenost je logaritamska.
maja (napisa): | jel mi moze neko rec kolka je slozenost algoritma binarno pretrazivanje |
Onako napamet... Ako imas n=2^k elemenata liste...
Prvo pregledavas niz duljine 2^k tako da provjeris onog u sredini, tj. sa indexom 2^{k-1}.
Ako nisi nasla element, pretrazujes niz (lijevi ili desni) duljine 2^{k-1}.
I tako u svakom koraku skratis niz na pola. Dakle, najveci broj koraka (tj. dijeljenja pocetnog n sa 2) je k = log_2 n.
Drugim rijecima, slozenost je logaritamska.
_________________ 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.
|