Započni novu temu Ova tema je zaključana, ne možete da menjate postove ili da odgovarate  [ 537 Posta ]  Idi na stranicu Prethodni  1 ... 17, 18, 19, 20, 21, 22  Sledeća
Autoru Poruka
 Tema posta:
PostPoslato: 20.09.2010. 01:03:28 
Korisnikov avatar

Pridružio se: 11.02.2009. 12:25:46
Postovi: 60
Godina: III
Smer: IS
Gandi je napisao:
Da li može da se ovako uradi onaj zadatak sa vraćanjem min el od putanje čvora do korena, kada su nam data ona 2 pokazivača... Ja sam predpostavio da imamo pokazivač na roditelja svakog čvora, pa bi to izgledalo ovako nekako


prvo... izem ti formatiranje :D but srsly, pretpostavljam da je do PHPBBa

elem
Kod:
public class CvorStabla {
   int podatak;
   CvorStabla levo;
   CvorStabla desno;
   CvorStabla roditelj;
   public CvorStabla (int p, CvorStabla l, CvorStabla d, CvorStabla r){
      podatak=p;
      levo=l;
      desno=d;
      roditelj=r;
   }


   public int vratiMin(CvorStabla koren, CvorStabla cvor)throws Exception { 
      
      if (koren == null) throw new Exception("Prazno drvce");  //
      
      int min = cvor.podatak
      CvorStabla pom = cvor;          
   
      while (pom != koren){
         
         pom = pom.roditelj; //menjas svoju pomocnu promenljivu, ne samo jedan njen atribut
         if (pom.podatak < min) min = pom.podatak;
   
      }
      return min;
   }
}


elem, komentari :P

Predlazem exception (na stranu sto je skolski), da ne bi bilo "A sta ako su ti svi podaci INT.MAX, a ti implementiras tako da ti to ignorise?"
Imao si return u while viska, to bi ti vracalo rezultat (i izlazilo iz metode) pri svakoj petlji (odnosno, prosao bi kroz petlju jednom, pa bi vratio vrednost)


Ostatak koda je relativno jasan IMO, ja sam samo malo smanjio broj linija koda promenom uslova u while... Ako nesto nije jasno, vikaj slobodno :)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 02:30:01 
Korisnikov avatar

Pridružio se: 18.12.2008. 00:45:39
Postovi: 100
Godina: III
Smer: IS
jel nekome radi sajt? pokusavam vec 3 dana da ga otvorim i ne radi :udri:

_________________
www.tutorijali.rs


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 02:56:12 
Korisnikov avatar

Pridružio se: 31.05.2009. 23:52:57
Postovi: 107
Lokacija: Blokovi batice...
Godina: II
Smer: IS
@Archduke
E hvala ti. Nego misliš da će ovo priznavati?? skapirao sam uglavnom sve i video sam da sam bzvz ubacio još jedan return.. Jel može ovo što si ti napisao samo bez Exception, i jel si zaboravio ili namerno izostavio onaj oseban slučaj što sam ja napisao kad je
if (koren == čvor) return koren.podatak...
I da ne radi sajt ni meni!!!

_________________
Partizane ti si najbolji,
u mom srcu jedini,
sve što imam, to je boja ta
CRNO-BELA!!!!


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 09:36:27 

Pridružio se: 16.09.2010. 16:11:03
Postovi: 11
Godina: II
Smer: IS
Gorbash je napisao:
mirche28 je napisao:
Ako neko zna da resi:

Dat je pokazivac na prvi element u JSListi celih br.Napisati metodu "Ubaci" koja ubacuje novi element nakon prvog elementa koji je veci od njega.Ako takav element ne postoji,novi element se ubacuje na krja liste.

Hvala ;)


public static void Ubaci(Element e) {
if (prvi == null) {
prvi = e;
return;
}
Cvor tekuci = prvi;
while (tekuci.sledeci != null) {
if (tekuci.broj > e.broj) {
e.sledeci = tekuci.sledeci;
tekuci.sledeci = e;

}
tekuci = tekuci.sledeci;
}
tekuci.sledeci = e;
}


sta ti je e? pps int..?


ja bih ovako uradio...

public void ubaci (cvorJSL prvi, int pod){

if (prvi==null){
cvorJSL novi=new cvorJSL(pod, null);
prvi=novi;
}

cvorJSL pom=prvi;

while(pom.sl!=null)
if (pom.pod>pom.sl.pod){
cvorJSL novi = new cvorJSL(pod,pom.sl);
pom=novi;
} else {

ubaciNaKraj(pod);
}
pom=pom.sl;
}
}

a,a??? sta mislite?? jel dobro???
:( :fokus:


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 10:14:36 

Pridružio se: 31.05.2010. 11:48:29
Postovi: 94
Godina: II
Smer: IS
dati primer za metodu olancavanje i otvorenog adresiranja?

objasni quick sort?

*nisam nasao u skripti pa ako nekog ne mrzi neka odgovori


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 10:50:33 

Pridružio se: 16.09.2010. 16:11:03
Postovi: 11
Godina: II
Smer: IS
elemeNt je napisao:
dati primer za metodu olancavanje i otvorenog adresiranja?

objasni quick sort?

*nisam nasao u skripti pa ako nekog ne mrzi neka odgovori


quick sort - verovatno najefikasniji alg za sortiranje.
Funkcionise tako sto prvo odaberemo neki element da bude pivot, zatim ostale elemente ispremestamo tako da prvo budu oni manji od pivota, a zatim oni veci. Za svaki od ova dva dela rekurzivno pozovemo quick sort.
Izuzetno lagan i lak za kodiranje. slozenost O(nlogn) - nije uvek ista, u najgorem slucaju O(n^2);


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 11:31:13 
Korisnikov avatar

Pridružio se: 11.02.2009. 12:25:46
Postovi: 60
Godina: III
Smer: IS
Gandi je napisao:
@ArchdukeJel može ovo što si ti napisao samo bez Exception, i jel si zaboravio ili namerno izostavio onaj oseban slučaj što sam ja napisao kad je
if (koren == čvor) return koren.podatak...


Kod:
CvorStabla pom = cvor;           
   
      while (pom != koren)


Ovde proveravas i taj uslov, odnosno ako je koren == cvor preskaces ceo while, i odma' ides na return (gde ti vraca cvor.podatak koji je minimum u skupu sebe samog :P )...

Tehnicki moze i bez exception, sa onim workaround-om koji si ti napisao, ali moze da ti ne da max broj poena za to... nije toliko strasan sistem izuzetaka, ubaci slobodno :)


theRockenrolla je napisao:
ja bih ovako uradio...

da ne quote-ujem ceo kod
:ucim:
nedostaje ti "{" kod while
nema potrebe da prosledjujes prvi, posto bi on trebalo da bude globalna promenljiva (mada nije greska per se). Takodje, ti uporedjujes "pom.pod>pom.sl.pod", a trebalo bi da uporedjujes sa podatak. Jos jedna stvar za koju mislim da bi ti skidali bodove jeste i koriscenje neimplementiranih metoda (UbaciNaKraj, mozda cak i koriscenje specijalnog konstruktora za CvorJSListe)... Posle malo formatiranja, mislim da moze ovako:
Kod:
public void ubaci (int target){

   //odma' pravis, posto ces ga sigurno ubaciti
   CvorJSListe newOne = new CvorJSListe();
   newOne.podatak =  target;
   
   //ako nema cvorova, onda samo kazes da je prvi nov, a nema sledeceg (Ostaje null za prvi.sledeci)
   if (prvi==null){
      prvi = newOne;
      return;
   }

   cvorJSL pom=prvi;


   //ako postoji jos neki element posle naseg pomocnog, pomocu break se izlazi iz while petlje
   while(pom.sledeci != null) {
      if (pom.podatak > target) break;
      pom = pom.sledeci;
   }

   //kada izadjes iz petlje, bilo da nema vise elemenata posle pom, ili da je pom veci od trazenog inta
   newOne.sledeci = pom.sledeci;   //radi i za pom.sledeci == null
   pom.sledeci = newOne;
}


Kao sto rekoh, ako nesto nisam objasnio, ili nije skroz jasno, samo vikajte :)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 11:45:07 

Pridružio se: 16.09.2010. 16:11:03
Postovi: 11
Godina: II
Smer: IS
mm da, da...
sad videh ovo za "pom.pod>pom.sl.pod".

zab sam da napisem, naravno, napisao bih i sta je metoda ubaci na kraj...


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 11:47:15 
Korisnikov avatar

Pridružio se: 11.02.2009. 12:25:46
Postovi: 60
Godina: III
Smer: IS
Kk, samo vodi racuna, meni deo poena nisu priznali zato sto sam koristio max(int1, int2) kao podrazumevanu funkciju :P


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 12:03:18 
Korisnikov avatar

Pridružio se: 17.06.2008. 21:02:21
Postovi: 127
Lokacija: FONfe
Godina: II
Smer: IS
1.Da li postoji slucaj kada je interpolaciono pretrazivanje sporije od binarnog pretrazivanja?Objasnite ga.
2.Objasnite postupak pretvaranja sume visegranskih stabla u jedno binarno stablo i dati primer.
3.Koliko cvorova ima kompletno binarno stablo reda 9?
Hvala! ;)

_________________
Nekada su devojke kuvale kao majke, sad piju kao ocevi.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 13:02:33 
Moderator
Korisnikov avatar

Pridružio se: 24.07.2006. 16:33:51
Postovi: 10041
Godina: Dipl.
Smer: IS
mirche28 je napisao:
1.Da li postoji slucaj kada je interpolaciono pretrazivanje sporije od binarnog pretrazivanja?Objasnite ga.
2.Objasnite postupak pretvaranja sume visegranskih stabla u jedno binarno stablo i dati primer.
3.Koliko cvorova ima kompletno binarno stablo reda 9?
Hvala! ;)


Kao i uvek, odgovor je na prethodnim stranama.

_________________
There are three things all wise men fear: the sea in storm, a night with no moon, and the anger of a gentle man.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 16:28:36 
Korisnikov avatar

Pridružio se: 24.12.2004. 10:55:55
Postovi: 99
Godina: Apsolvent
Smer: IS
Da li može neko da napiše metode koje implementiraju algoritam za interpolaciono pretraživanje niza celih brojeva sortiranog 1) u opadajućem i 2) rastućem redosledu?


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 21:38:58 

Pridružio se: 01.02.2009. 15:38:26
Postovi: 310
Godina: Dipl.
Smer: IS
Koliko traje ispit?


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 21:54:49 

Pridružio se: 31.10.2008. 16:00:46
Postovi: 17
Godina: II
Smer: IS
Trebalo bi 2h.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 22:02:45 
Korisnikov avatar

Pridružio se: 22.10.2007. 22:39:12
Postovi: 374
Godina: Apsolvent
Smer: IS
Ajde da ponovim, možda neko zna odgovor.
Corey je napisao:
Jel može hashing malo prostije da se kaže od ovoga

4. Hashing (olancavanje, otvoreno adresiranje)
Prva tehnika se naziva otvoreno adresiranje. Kada se primenom funkcije h(k) dobije adresa koja je vec zauzeta, tada se na dobijenu vrednost primenjuje nova funkcija r(k). Ona se primenjuje sve dok se dobije slobodna adresa. Najjednostavnija funkcija r(k) je ri+1(k)=ri(k)+1, r1(k)=h(k)+l, tj. funkcija cija vrednost je sledeca adresa u odnosu na prethodno izracunatu adresu. Ovom metodom se zapravo sekvencijalno, linearno ispituju adrese sve dok se ne nade slobodna adresa. Zato se ova metoda naziva linearno probanje.
Druga tehnika problem kolizije rešava olancavanjem zapisa ciji kljucevi imaju istu vrednost za h(k). Za smeštanje olancanih zapisa se može koristiti isti memorijski prostor kao i za ostale zapise bez kolizije tzv. primarni prostor a može se i rezervisati poseban prostor za njih. U prvom slucaju se zauzima manje prostora, tj. efikasnije se koristi prostor ali može dovesti do povecanog broja kolizija. Naime, smeštanjem zapisa cije adrese su zauzete u primarni prostor se zapravo zauzimaju adrese za neke zapise koje bi oni dobili sa funkcijom h(k). Slucaj da jedan zapis primenom funkcije h(k) dobije adresu koja je zauzeta od strane zapisa cija vrednost h(k) nije ta adresa se naziva sekundarno grupisanje.

I na primer ovo


1. Robusno interpolaciono pretrazivanje.
Postoji veza izmedju vrednosti kljuca u skupu vrednosnih kljuceva i pozicije u nizu zapisa sa tim kljucem, na osnovu koje se moze izracunati (interpolirati) pozicija trazenog elementa. Robusno interpolaciono pretrazivanje je brzo pretrazivanje, jer se uvodi promenljiva R (razmak) tako da je uvek Pk-Pmin i Pmax-Pk vece od R.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 20.09.2010. 22:31:12 
Korisnikov avatar

Pridružio se: 11.02.2009. 12:25:46
Postovi: 60
Godina: III
Smer: IS
Vec je prilicno lepo objasnjeno, ali hajde da probam da sazmem :)

4. Hashing (olancavanje, otvoreno adresiranje)
Prva tehnika se naziva otvoreno adresiranje. Kada se primenom funkcije h(k) dobije adresa koja je vec zauzeta, tada se na dobijenu vrednost primenjuje nova funkcija r(k). Ona se primenjuje sve dok se dobije slobodna adresa. Najjednostavnija funkcija r(k) je ri+1(k)=ri(k)+1, r1(k)=h(k)+l, tj. funkcija cija vrednost je sledeca adresa u odnosu na prethodno izracunatu adresu. Ovom metodom se zapravo sekvencijalno, linearno ispituju adrese sve dok se ne nade slobodna adresa. Zato se ova metoda naziva linearno probanje.


Otvoreno adresiranje - ako hash funkcija za dva unosa daje istu adresu (odnosno za neki unos daje popunjenu adresu), onda se najcesce unos zapisuje u sledecu slobodnu adresu (alternativna funkcija predstavlja inkrementiranu originalnu funkciju, koliko god puta treba do slobodnog mesta)


Druga tehnika problem kolizije rešava olancavanjem zapisa ciji kljucevi imaju istu vrednost za h(k). Za smeštanje olancanih zapisa se može koristiti isti memorijski prostor kao i za ostale zapise bez kolizije tzv. primarni prostor a može se i rezervisati poseban prostor za njih. U prvom slucaju se zauzima manje prostora, tj. efikasnije se koristi prostor ali može dovesti do povecanog broja kolizija. Naime, smeštanjem zapisa cije adrese su zauzete u primarni prostor se zapravo zauzimaju adrese za neke zapise koje bi oni dobili sa funkcijom h(k). Slucaj da jedan zapis primenom funkcije h(k) dobije adresu koja je zauzeta od strane zapisa cija vrednost h(k) nije ta adresa se naziva sekundarno grupisanje.

Olancavanje zapisa je drugo resenje kolizije, koje pored prvog unosa sadrzi i pokazatelj ka memorijskom mestu gde se nalazi sledeci unos sa istom vrednoscu hash funkcije. Ta memorijska mesta za druge(trece, cetvrte) unose moze da bude ili u posebnom memorijskom prostoru (bolje za implementaciju, ali vise mesta zauzima) ili u primarnom mem. prostoru (gde vec cuvas podatke, manje mesta se koristi, ali moze da dovede do kolizije (koja se u tom slucaju zove sekundarno grupisanje))

Za RIP verovatno moze slicno da se izvuce, samo proanaliziraj obicno interpolaciono (ako tako nesto postoji) i nadji razlike... Ne mogu da se setim sada svega :P


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 21.09.2010. 15:23:51 
Korisnikov avatar

Pridružio se: 12.02.2009. 06:32:24
Postovi: 172
Godina: IV
Smer: IS
21.09.2010.
prva grupa drugi deo:

(II kolokvijum)

5. Pokazati postupak formiranja B* stabla celih brojeva koje ima maksimalno 2 ključa u čvoru, kada se u prazno stablo ubacuju elementi 3, 14, 47, 81, 64, 25, 43 i 50, a zatim iz dobijenog stabla izbace elementi 3, 25 i 64. Svaki korak svake operacije posebno nacrtati!
(13 poena)

6. Pokazati postupak formiranja AVL stabla celih brojeva, kada se u prazno stablo ubacuju elementi 3, 14, 47, 81, 64, 25, 43 i 50. Svaki korak svake operacije posebno nacrtati!
(12 poena)

7. Dat je pokazivač na koren binarnog stabla celih brojeva. Napišite algoritam koji će dato stablo urediti tako da za svaki čvor važi da je element u njemu veći od elemenata njegove dece.
(15 poena)

(II domaći)

8. Šta je graf (mreža) i koji su njegovi elementi (opišite ih).
(10 poena)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 21.09.2010. 18:12:16 
Korisnikov avatar

Pridružio se: 28.06.2010. 20:32:59
Postovi: 155
Lokacija: Patuljak
Godina: Apsolvent
Smer: IS
Gorbash je napisao:
Lol, to nije tacno. Vrte se maltene ista pitanja uvek, pogledaj samo rokove.

Citiraj:

19. Da li postoji slucaj kada je interpolaciono pretrazivanje brze od binarnog pretrazivanja?
Kada se trazeni element nalazi “slepljen” uz desnu ili levu ivicu skupa koji se pretrazuje, jer se tada binarno pretrazivanje degenerise u sekvencijalno.



E, zbog tebe cu pasti strukture! PA sto stavljas pogresne odgovoreeeeeee?!?!?!?!??!?!?!?! Ovo nije tacno, a ja tako naucila!
a i ja sam majmun sto ne proveravam! :udri: :udri: :udri:

_________________
Shine on you crazy diamond..


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 21.09.2010. 20:44:40 
Korisnikov avatar

Pridružio se: 31.05.2009. 23:52:57
Postovi: 107
Lokacija: Blokovi batice...
Godina: II
Smer: IS
ŠTa je tebi? Ovo pitanje je tačno skroz.. Pogledaj bilo koju skriptu i videćeš ovakav odgovor.. Što optužuješ čoveka za džabe:))

_________________
Partizane ti si najbolji,
u mom srcu jedini,
sve što imam, to je boja ta
CRNO-BELA!!!!


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 21.09.2010. 20:53:22 

Pridružio se: 25.11.2009. 13:43:06
Postovi: 81
Godina: IV
Smer: IS
GANDI, nadam se da si u pravu! Mrzi me da listam skripte ali lik koji inace drzi casove iz SPA nam je u fonfeu rekao da to nije tacno... pa zato devojka optuzuje ;)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 21.09.2010. 21:09:32 
Korisnikov avatar

Pridružio se: 11.02.2009. 12:25:46
Postovi: 60
Godina: III
Smer: IS
Mislim da su Gorbash i Gandi u pravu, tacan je odgovor... Ako razmislite sa velikim brojevima, videcete i koja je razlika :)

Zamislite da pokusavate da doprete do recimo prvog-drugog telefonskog broja u imeniku od 2M Beogradjana... Binarno stalno ide stalno na pola intervala (1M, 0.5M, 0.25M....), dok bi interpolaciono (pod uslovom da je raspored prezimena relativno uniforman) odmah otislo na 66K (prvu tridesetinu)... i nastavak trazenja bi bio u slicnom maniru brzi...




Sada, pitanje je ŠBBKBB slepljeni uz ivicu i da nisu uniformno rasporedjeni :D
P.S. verovatno se niste lepo razumeli sa uciteljem... ili se zbunio :)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 21.09.2010. 21:30:45 
Korisnikov avatar

Pridružio se: 31.05.2009. 23:52:57
Postovi: 107
Lokacija: Blokovi batice...
Godina: II
Smer: IS
Archduke... Iskreno ja sam sao naučio,a tako je u svakoj skripti.. Al dobro sad mi je još više pomoglo ovo tvoje objašnjenje :)
@anchee~89
Ja sam imao drugu grupu, al nadam se da sam upravu.. Za pitanje kada je lošije , sporije
interpolaciono pretrazivanje od binarnog, ja sam samo napisao da je to kada raspodela nije uniformna... Jel to dobro ili ne :zbun: ili treba još nešto :( ????

_________________
Partizane ti si najbolji,
u mom srcu jedini,
sve što imam, to je boja ta
CRNO-BELA!!!!


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 22.09.2010. 08:12:39 
Korisnikov avatar

Pridružio se: 28.06.2010. 20:32:59
Postovi: 155
Lokacija: Patuljak
Godina: Apsolvent
Smer: IS
Gandi je napisao:
Archduke... Iskreno ja sam sao naučio,a tako je u svakoj skripti.. Al dobro sad mi je još više pomoglo ovo tvoje objašnjenje :)
@anchee~89
Ja sam imao drugu grupu, al nadam se da sam upravu.. Za pitanje kada je lošije , sporije
interpolaciono pretrazivanje od binarnog, ja sam samo napisao da je to kada raspodela nije uniformna... Jel to dobro ili ne :zbun: ili treba još nešto :( ????


I ja sam bila II grupa. Pitanje je kada je brze, a ne kada je sporije i odgovorila sam kako je Gorbash napisao i izgleda da nije tacno, potvrdili mi ljudi..

Archduke je napisao:
Mislim da su Gorbash i Gandi u pravu, tacan je odgovor... Ako razmislite sa velikim brojevima, videcete i koja je razlika :)

Zamislite da pokusavate da doprete do recimo prvog-drugog telefonskog broja u imeniku od 2M Beogradjana... Binarno stalno ide stalno na pola intervala (1M, 0.5M, 0.25M....), dok bi interpolaciono (pod uslovom da je raspored prezimena relativno uniforman) odmah otislo na 66K (prvu tridesetinu)... i nastavak trazenja bi bio u slicnom maniru brzi...




Sada, pitanje je ŠBBKBB slepljeni uz ivicu i da nisu uniformno rasporedjeni :D
P.S. verovatno se niste lepo razumeli sa uciteljem... ili se zbunio :)


"Pod pretpostavkom da su kljucevi uniformno rasporedeni, interpolaciono pretraživanje
zahteva prosecno log2(log2N) poredenja, što je bolje od binarnog pretraživanja.
Medutim ako kljucevi nisu uniformno rasporedeni tad performanse algoritma mogu biti
znatno pogoršane. U najgorem slucaju, vrednost Pk može biti Pmin+ 1 ili Pmax - 1 odnosno
interpolaciono pretraživanje se degeneriše u sekvencijalno (dok binarno i u najgorem slucaju
ostaje log2 N)."

Dakle, kada je interpolaciono BRZE od binarnog? Sigurno nije onako kako je Gorbash napisao.

_________________
Shine on you crazy diamond..


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 22.09.2010. 11:44:53 
Korisnikov avatar

Pridružio se: 11.02.2009. 12:25:46
Postovi: 60
Godina: III
Smer: IS
goggga je napisao:
"Pod pretpostavkom da su kljucevi uniformno rasporedeni, interpolaciono pretraživanje zahteva prosecno log2(log2N) poredenja, što je bolje od binarnog pretraživanja.


Dovoljan odgovor :P

U najgorem slucaju za binarno (kada se trazi prvi/poslednji, odnosno "slepljeni" unos) kazes da je log2N (pardon, pozaboravljao sam sve te brojeve). Ukoliko pretpostavimo da je raspodela unosa u strukturu relativno uniformna, onda je broj interpolacionih log2(log2N)... za 666 unosa, binarno bi radilo 10 iteracija, dok bi interpolaciono radilo 4 iteracije...

Znaci, ukoliko su podaci koliko-toliko standardni, interpolaciono bi trebalo da je brze ako je unos koji se trazi blizu ivice...


P.S. nisam siguran, sa kojim delom se ne slazes, posto mislim da pricamo istu stvar :)

Edit: moze da se desi da se lose secam, ipak odavno nisam razmisljao o tome... ali mislim da je okej)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
 Tema posta:
PostPoslato: 22.09.2010. 11:56:23 
Korisnikov avatar

Pridružio se: 28.06.2010. 20:32:59
Postovi: 155
Lokacija: Patuljak
Godina: Apsolvent
Smer: IS
znam da treba da se napise da je uniformna raspodela kada je interppolaciono brze od binarnog. i samo to treba. ali ono za slepljeni element itd ne treba, tada interpolaciono nije brze. tu je gorbash pogresio. eto. malopre sam pitala profesora, na faxu sam, i rece mi da treba da se napise kod tog odg samo da je uniformna raspodela.

_________________
Shine on you crazy diamond..


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
Prikaži postove u poslednjih:  Poređaj po  
Započni novu temu Ova tema je zaključana, ne možete da menjate postove ili da odgovarate  [ 537 Posta ]  Idi na stranicu Prethodni  1 ... 17, 18, 19, 20, 21, 22  Sledeća


Ko je OnLine

Korisnici koji su trenutno na forumu: Google [Bot] i 15 gostiju


Ne možete postavljati nove teme u ovom forumu
Ne možete odgovarati na teme u ovom forumu
Ne možete monjati vaše postove u ovom forumu
Ne možete brisati vaše postove u ovom forumu
Ne možete slati prikačene fajlove u ovom forumu

Pronađi:
Idi na:  
cron
Copyleft FONForum 2001-2014 | Powered by phpBB © phpBB Group