Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Nalazenje svih parova brojeva ...

[es] :: Art of Programming :: Nalazenje svih parova brojeva ...

[ Pregleda: 4440 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

farstar

Član broj: 52375
Poruke: 107
*.ptt.yu.



Profil

icon Nalazenje svih parova brojeva ...05.09.2005. u 05:43 - pre 225 meseci
Da li je neko negde naisao na sledeci za****k, odnosno njegovo resenje:

Dat je niz celih brojeva a=(a1,a2,...,an). Konstruisati algoritam slozenosti
manje od O(n^2) za nalazenje svih parova (i,j) takvih da se binarni zapisi
brojeva ai i aj ne razlikuju na vise od 2 mesta.
 
Odgovor na temu

gpreda
Goran Predovic
Kragujevac

Član broj: 19087
Poruke: 74
80.93.227.*

Sajt: alas.matf.bg.ac.yu/~mr990..


Profil

icon Re: Nalazenje svih parova brojeva ...05.09.2005. u 12:44 - pre 225 meseci
Nisam siguran da si lepo postavio zadakat.

Samo da bi ispisao sve kombinacije kojih moze biti O(n2) treba ti O(n2) vremena.
 
Odgovor na temu

farstar

Član broj: 52375
Poruke: 107
*.vdial.verat.net.



Profil

icon Re: Nalazenje svih parova brojeva ...05.09.2005. u 18:48 - pre 225 meseci
Trivijalni algoritam proverava svaki broj sa svakim brojem
i tu imamo slozenost O(n^2).

Ako skoro svi brojevi zadovoljavaju trazeni uslov onda je
opet slozenost O(n^2).

Ali ako malo brojeva recimo k (k << n) zadovoljava trazeni
uslov onda bi nekim efikasnijim algoritmom od trivijalnog za
te slucajeve slozenost bila manja od O(n^2), a u slucaju
kad skoro svi brojevi zadovoljavaju uslov onda bi naravno i
slozenost efikasnijeg algoritma od trivijalnog isto bila O(n^2).

Znaci problem bi bio naci algoritam koji je efikasan za
slucajeve sa malo brojeva koji zadovoljavaju uslov zadatka
i za te slucajeve ima manju slozenost od O(n^2).


[Ovu poruku je menjao farstar dana 05.09.2005. u 19:52 GMT+1]
 
Odgovor na temu

boba5555
Slobodan Mitrovic
Deronje

Član broj: 49685
Poruke: 37
*.metrohive.net.

Sajt: www.kaziprst.com/slobodan


Profil

icon Re: Nalazenje svih parova brojeva ...12.09.2005. u 20:15 - pre 225 meseci
Da li bi pomoglo kad bi ti sam generisao te brojeve? Znaci da imash algoritam koji ce prvo praviti sve brojeve koji se razlikuju za jednu binarnu cifru, pa onda za dve. Koliko sam shvati to je u stvari jedna, odnosno dve promene cifre, promene cifara na dva mesta. Trebalo bi da radi.
Nadam se da sam pomogao. Slozenost je svakako manja od n^2!!!
....
Slobodan
 
Odgovor na temu

[es] :: Art of Programming :: Nalazenje svih parova brojeva ...

[ Pregleda: 4440 | Odgovora: 3 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.