Algoritmi - problem

runner · **Poslato:** 01.12.2012. 20:44:04

Imam jedan zanimljiv algoritamski problem

Naime, imam listu koja nije sortirana (i nema duplikata). U listi se nalazi običan zapis(ili objekat, kako vam drago) koji ima dva polja (atributa). Jedno polje je string a drugo intidžer. Npr. da bi lakše zamislili, recimo da imamo listu osoba i pri tome svaka osoba ima ime kao prvo polje i starost u godinama kao drugo polje. Trebaju mi imena najstarijih osoba. Dakle vodite računa da se može desiti da samo jedna osoba bude najstarija, a može se desiti i da ih ima više.
Da li je moguće dobiti traženi rezultat kroz samo jednu iteraciju ili mora ipak kroz dve? Još uvek razmišljam, ali za sad ne mogu da smislim algoritam koji bi sve to radio kroz jednu iteraciju.

Darth Neman · **Poslato:** 01.12.2012. 21:55:11

Moguce je u O(n) naci najstarije osobe ali uz dodatnu memoriju...

runner · **Poslato:** 01.12.2012. 22:12:00

tj uz "kvazi sortiranje". Na to si mislio?

Darth Neman · **Poslato:** 01.12.2012. 22:26:56

Ne, bez sortiranja. Na sortiranje ti u startu ode O(nlogn) + ti ode makar O(n) na trazenje liste najvecih elemenata.

Evo koda za ovo moje uz ogranicenje da mozda i nije toliko dobro ali postuje to ogranicenje o jednom prolasku kroz listu:

Kod:

...sve inicijalizacije listi itd. itd. itd.

maxEl = unsortedArray[0];
oldestGuys = new ArrayList();
oldestGuys.add(maxEl);
for (int i=1; i<unsortedArray.size(); i++){
   if (unsortedArray[i] > oldestGuys[0]){
      clearOldestGuys();
      oldestGuys.add(unsortedArray[i]);
   }
   if (unsortedArray[i] == oldestGuys[0]){
      oldestGuys.add(unsortedArray[i]);
   }
}
return oldestGuys;

E sad najveci problem imas na liniji clearOldestGuys() jer tu u zavisnosti od programskog jezika treba da nadjes resenje kako ocistiti listu a da ne dobijes jos vremena za trosenje u algoritmu. Ako je u pitanju npr. Java onda prostom inicijalizacijom nove liste gubis staru listu i ostavljas GC da resi posao. U nekom drugom jeziku bi morao da prodjes kroz celu listu i da eliminises element po element liste. Tu u najgorem slucaju dolazis do O(n^2) gde resenje o dva prolaska kroz listu vise ne izgleda kao lose resenje

runner · **Poslato:** 01.12.2012. 22:59:20

da, da na to sam mislio samo nisam našao najspretniji izraz... možda bi bilo bolje da sam nazvao "trenutno grupisanje"

jer ti tu zapravo grupišeš osobe sa istim godinama starosti, s tim što se pravi grupa samo za trenutno najveću godinu starosti, ali se ide u rastućem redosledu (zato me povuklo na sortiranje).
Međutim još ne mogu da prihvatim činjenicu da stvarno ne može prostije od dve iteracije (ili ove varijante sa grupisanjem u Java slučaju)!

zlatko · **Poslato:** 01.12.2012. 23:26:35

Darth je dao dobar odgovor. U javi se clearOldestGuys() može uraditi sa pozivom na clear() ali ta metoda iterira nad svim njenim elementima. Lakše je odbaciti ceo objekat liste.

Darth Neman · **Poslato:** 01.12.2012. 23:31:23

@runner:
moze prostije... da krenes da vodis racuna kako ubacujes elemente u tu listu pa da ona bude uvek sortirana...

jos samo malo · **Poslato:** 03.12.2012. 01:43:54

Darth Neman je napisao:

@runner:
moze prostije... da krenes da vodis racuna kako ubacujes elemente u tu listu pa da ona bude uvek sortirana...

Ovo.

Ili, cuvas mapu gde je key godina starosti a value lista imena i broj koji oznacava trenutno najstarije osobe.

runner · **Poslato:** 03.12.2012. 04:45:18

e vidiš, ovo drugo je zanimljivo rešenje

jos samo malo · **Poslato:** 03.12.2012. 08:14:43

Zaboravih, za ubacivanje u listu tako da je sortirana je potrebno da se ne koristi lista vec neka forma binary tree-ja, inace je i ovo O(n^2).

Ili, samo uporedis sa prvim elementom iz liste i ubacis sa leve strane ako je >=. Ako je < ionako ti ne treba.

Naravno, ako imas GC onda je prvo ponudjeno resenje sa ponovnom inicijalizacijom liste jednostavnije, a mi ovde dzaba pricamo.

FONForum

Algoritmi - problem

Ko je OnLine