Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

binarno pretrazivanje
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
maja
Gost





PostPostano: 10:58 ned, 19. 1. 2003    Naslov: binarno pretrazivanje Citirajte i odgovorite

jel mi moze neko rec kolka je slozenost algoritma binarno pretrazivanje

hvala
jel mi moze neko rec kolka je slozenost algoritma binarno pretrazivanje

hvala


[Vrh]
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 15:55 ned, 19. 1. 2003    Naslov: Re: binarno pretrazivanje Citirajte i odgovorite

[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.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2 Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan