|
Programiranje Programski jezici, tehnike, alatke... |
|
Alatke vezane za temu | Vrste prikaza |
1.6.2011, 16:45 | #21 |
Član
Član od: 16.4.2010.
Lokacija: Pančevo
Poruke: 462
Zahvalnice: 41
Zahvaljeno 68 puta na 63 poruka
|
Re: Optimalni algoritam?
Lol, pa ne baš previše, jer svaki niz već ima svoj index od 0 do n, samo to treba iskorisiš.
Kolko sam shvatio njemu treba najmanji broj koraka, a ne implementacija algoritma. |
1.6.2011, 17:01 | #22 | |
V.I.P. Programiranje
Član od: 29.8.2007.
Lokacija: Valjevo
Poruke: 1.349
Zahvalnice: 983
Zahvaljeno 371 puta na 280 poruka
|
Re: Optimalni algoritam?
Netreba mu, ima bolje resenje:
@Geomaster citat Citat:
|
|
1.6.2011, 19:06 | #23 |
Starosedelac
Član od: 10.8.2007.
Lokacija: Temples of Syrinx
Poruke: 2.193
Zahvalnice: 417
Zahvaljeno 1.006 puta na 568 poruka
|
Re: Optimalni algoritam?
|
Sledećih 6 korisnika se zahvaljuje korisniku Sun Tzu na korisnoj poruci: | ||
Belphegor (1.6.2011), doctor (1.6.2011), Geomaster (1.6.2011), Nikola16789 (2.6.2011), NISAM NESTO SMART (1.6.2011), Todors (1.6.2011) |
1.6.2011, 21:57 | #24 | |
V.I.P. Programiranje
|
Re: Optimalni algoritam?
Citat:
I hvala svima koji su pomogli Mada hookovanje bi trebalo da pomogne. Poslednja ispravka: Geomaster (2.6.2011 u 12:26) Razlog: nisam baš toliko dobar u kucanju sa isključenim monitorom |
|
2.6.2011, 0:37 | #25 |
Član
Član od: 30.10.2005.
Lokacija: Vancouver, BC
Poruke: 475
Zahvalnice: 48
Zahvaljeno 95 puta na 75 poruka
|
Re: Optimalni algoritam?
Quicksort ne sortira niz u najmanjem broju koraka, daleko od toga, već ima najbolju vremensku složenost, nlogn.
|
2.6.2011, 10:40 | #26 |
Član
Član od: 16.4.2010.
Lokacija: Pančevo
Poruke: 462
Zahvalnice: 41
Zahvaljeno 68 puta na 63 poruka
|
Re: Optimalni algoritam?
Pa dobro, verovatno da nije, jer postoje i hibridni algoritmi. Ovo je najbrži za koji ja znam i koji se najviše koristi u te svrhe. Koji mu ti preporučuješ?
|
2.6.2011, 12:29 | #27 |
V.I.P. Programiranje
|
Re: Optimalni algoritam?
|
2.6.2011, 12:34 | #28 | |
V.I.P. Programiranje
Član od: 29.8.2007.
Lokacija: Valjevo
Poruke: 1.349
Zahvalnice: 983
Zahvaljeno 371 puta na 280 poruka
|
Re: Optimalni algoritam?
Citat:
http://en.wikipedia.org/wiki/Time_complexity Msilim da je std::sort brzi od qsort. |
|
2.6.2011, 12:59 | #29 | |
V.I.P. Programiranje
|
Re: Optimalni algoritam?
Citat:
Vremenska kompleksnost ovde je broj upoređivanja, ne broj swapova (jedan element može da se swapuje više puta pre nego što zauzme svoju konačnu poziciju). std::sort zavisi mnogo od implementacije, u standardu nije naveden koji tačno algoritam treba da se koristi, neke implementacije koriste quicksort, a neke introsort. Btw, ne uspevam da hookujem OGL-ove funkcije, ili ne radi ili se program sruši |
|
2.6.2011, 13:04 | #30 |
V.I.P. Zaštita
Član od: 30.9.2007.
Lokacija: Hypnos Control Room, Tokyo Metropolitan Government Building
Poruke: 5.914
Zahvalnice: 1.181
Zahvaljeno 1.320 puta na 1.094 poruka
|
Re: Optimalni algoritam?
http://en.wikipedia.org/wiki/Sorting_algorithm
Najbrži ili najbolji algoritam nepostoji. Svaki od njih ima svoje prednosti i mane u odnosu na druge u datim situacijama. Osim, vremesnke kompleksnoti bitna je i stabilnost algoritma i worst time. Potražite ovu knjigu: http://www.sk.rs/forum/showthread.php?t=33731 |
2.6.2011, 13:09 | #31 | |
V.I.P. Programiranje
|
Re: Optimalni algoritam?
Citat:
|
|
2.6.2011, 13:33 | #32 |
Član
Član od: 16.4.2010.
Lokacija: Pančevo
Poruke: 462
Zahvalnice: 41
Zahvaljeno 68 puta na 63 poruka
|
Re: Optimalni algoritam?
Koristi ti qsort i uživaj, ne verujem da ćeš sam napraviti bolji algoritam. Pokušao sam da nađem na googlu algoritam koji najmanje swopuje ali izgleda da se ljudi nisu time mnogo bavili, već su to samo poređenja kompleksnoti.
|
3.6.2011, 0:24 | #34 |
Član
Član od: 30.10.2005.
Lokacija: Vancouver, BC
Poruke: 475
Zahvalnice: 48
Zahvaljeno 95 puta na 75 poruka
|
Re: Optimalni algoritam?
Mislim da ljudi ovde pričaju o dve različite stvari. Jedno je brzina algoritma (odnosno vremenska složenost), a drugo minimalan broj zamena. Ako pričamo o prvom, Quicksort jeste među bržima. Međutim, ako modifikujemo algoritam tako da pamti broj zamena, videćemo na kraju da je taj broj veći od N, za određene test primere.
Sa druge strane, očigledno je da je u najgorem slučaju potrebno najviše N-1 zamena: prva zamena postavi prvi element na svoje mesto, druga drugi element itd. Kada postavimo pretposlednji element, automatski će nam biti postavljen i poslednji. U praksi, ovaj broj zamena je i manji. Pritom, da bismo odredili broj zamena, uopšte nema potrebe da zapravo sortiramo taj niz, pre će biti da je tu u pitanju posmatranje niza kao graf. Tačnije... http://online-judge.uva.es/board/vie...ba2ba4#p101543 |
Sledeći korisnik se zahvaljuje korisniku pyost na korisnoj poruci: | ||
Geomaster (3.6.2011) |
3.6.2011, 10:30 | #35 | |
V.I.P. Programiranje
|
Re: Optimalni algoritam?
Citat:
Iskopao sam ovo, a na linku piše da je ovo NP-hard problem. Tačno kao što su na linku spomenuli, rešenje je očigledno kada su elementi jedinstveni, ali ja imam slučaj sa dosta ponavljanja. |
|
4.6.2011, 11:41 | #36 |
Starosedelac
|
Re: Optimalni algoritam?
Najmanji broj swapova je broj elemenata koji nisu na svom mestu - 1.
Primer: 1 3 2 2 i 3 nisu na svom mestu = 2 elementa = 2 - 1 = 1 1 4 2 3 5 4, 2 i 3 nisu na svom mestu = 3 elementa = 3 - 1 = 2 (recimo, zamenimo 4 i 2, pa 3 i 4 i imamo 1 2 3 4 5) Valjda bi trebalo da radi za sve nizove |
4.6.2011, 13:57 | #37 | |
Član
Član od: 15.12.2010.
Lokacija: Beograd
Poruke: 120
Zahvalnice: 26
Zahvaljeno 39 puta na 32 poruka
|
Re: Optimalni algoritam?
Citat:
Maksimalni broj swapova koji nam daje rešenje je broj elemenata koji nisu na svom mestu -1, ali ne i najmanji. Uzmi na primer niz 1,3,4,2,6,7,5. Šest elemenata nije na svom mestu a treba nam samo četiri swapa (2,3)(3,4)(5,6)(6,7). |
|
Bookmarks sajtovi |
|
|
Slične teme | ||||
tema | temu započeo | forum | Odgovora | Poslednja poruka |
algoritam | rile | Programiranje | 6 | 6.3.2019 0:53 |
Algoritam za registraciju programa!!! | Todors | Programiranje | 10 | 19.8.2010 16:19 |
C# Euklidov Algoritam : POMOC! | Nix29 | Programiranje | 1 | 30.4.2010 21:24 |
Optimalni procesor za odredjenu graficku | Predrag Stankovic | Grafika | 20 | 21.8.2007 1:25 |
Problem algoritam i program | mikica | Programiranje | 3 | 27.11.2006 17:21 |