2. sada domácich zadaní
Najneskorší termín odovzdania: 4.3.2013 (pondelok) o 9:50
Odovzdávané súbory: AdamSort.java
Doplňujúce požiadavky:
- riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
- zdrojový kód správne naformátujte (CTRL+SHIFT+F),
- komentovaný zdrojový kód je vítaný
Oóóóóó (3 body)
2 body: Na cvičeniach vám cvičiaci spomínali, že pri asymptotickej časovej zložitosti na základe logaritmu nezáleží. Aby ste sa o tom presvedčili, formálne dokážte:
(d+50)*logm+2(n) = O(log2 n), kdedje deň vášho narodenia amje mesiac vášho narodenia.
1 bod: Zoraďte jednotlivé funkcia podľa O-notácie tak, aby ak je funkcia f pred funkciou g, potom f = O(g). Hodnotu d nahraďte dňom vášho narodenia a hodnotu m mesiacom vášho narodenia.
2n-23*n3 - m*n(d+5)*n + log(n)n + d52*n2*log10(n)
Riešenie tejto úlohy odovzdajte v písomnej podobne svojmu cvičiacemu alebo najneskôr 4.3.2013 pred prednáškou.
Geniálny algoritmus (5 bodov)
Adam sa zúčastnil 2. prednášky z PAZ1b, kde bolo prezentované binárne vyhľadávanie v usporiadanej postupnosti v čase O(log n), triedenie výberom a bublikové triedenie bežiace v čase O(n2).
Adam bol fascinovaný triediacimi (usporadúvacími) algoritmami. Začal googliť a na YouTube našiel aj tieto videá:
Keď ich tak pozeral, chytrý algoritmus analyzujúci "divákov" na YouTube sa rozhodol Adamovi odporučiť na pozretie aj toto video: http://www.youtube.com/watch?v=k4RRi_ntQc8 Jeho pozretie výrazne zmenilo Adamov život (teda aspoň na pár najbližších hodín). Keď Obama tvrdí, že BubbleSort (bublinkové triedenie) nie je ta správna cesta ako "sortovať", znamená to, že musí existovať niečo lepšie (čo určite FBI, CIA, NSA a ktovie kto ešte pred svetom dôkladne strážia). Pred Adamom teraz stála jasná výzva: nájsť lepší algoritmus. Po intenzívnom rozmýšľaní prišiel s geniálnou stratégiou pre triediaci algoritmus, ktorý by mal mať asymptoticky lepšiu časovú zložitosť ako triedenie výberom, či bublinkové triedenie. Jeho stratégia vychádzala z tejto úvahy:
Predpokladajme, že máme utriediť n čísel. Riešme teda menší problém a nejako rekurzívne utrieďme n-1 čísel. Konkrétne, rekurzívne utrieďme prvých n-1 čísel v poli a číslo na poslednom indexe nechajme tak. Aby sme dostali utriedenú postupnosť n čísel, ostáva nám už len umiestniť číslo na poslednom indexe na správne miesto. Nuž a toto miesto (index) vieme predsa nájsť binárnym vyhľadávaním v čase O(log n). Celková zložitosť algoritmu by tak mala byť lepšia, pretože to, čo vlastne robíme je, že n krát vkladáme číslo (najprv na indexe 0, potom 1, 2, ..., n-1) do nejakej už utriedenej postupnosti s využitím binárneho vyhľadávania s logaritmickou časovou zložitosťou.
4 body: Na základe Adamovej myšlienky implementujte nerekurzívny triediaci algoritmus (metóda utried v nižšie uvedenej triede AdamSort).
1 bod: Analyzujte Adamov algoritmus. Bude jeho stratégia fungovať, t.j. budú sa dať nejako takto utriediť čísla? Akú časovú zložitosť bude mať algoritmus založený na tejto stratégii? Je pravda, že sa mu podarí skonštruovať algoritmus, ktorý bude asymptoticky lepší ako triedenie výberom alebo bublinkové triedenie? Svoje odpovede zdôvodnite a podporte argumentami. V písomnej podobe ich odovzdajte cez Moodle (ako komentár k odoslanej implementácii triedy AdamSort alebo ako samostatný textový súbor).
Poznámka: Ako odpovedať stručne na otázky o časovej zložitosti (samozrejme v prípade, že algoritmus funguje)?
- Časová zložitosť Adamovho algoritmu v najhoršom prípade je
O(T(n)), pretože ... - Záver:
- Ak
T(n) = n2, potom Adamov algoritmus má rovnakú asymptotickú zložitosť ako triedenia z prednášky. - Ak
T(n)nie je vO(n2), potom Adamov algoritmus má asymptoticky horšiu časovú zložitosť ako algoritmy z prednášky. - Ak
n2nie je vO(T(n)), potom Adamov algoritmus má asymptoticky lepšiu časovú zložitosť než algoritmy z prednášky.
- Ak
public class AdamSort {
/**
* Vrati index v poli p, kde by sa mal nachadzat prvok so zadanou hodnotou v
* zadanom usporiadanom podpoli pola p.
*
* @param p
* pole
* @param odIdx
* index prveho prvku usporiadaneho podpola
* @param poIdx
* index posledneho prvku usporiadaneho podpola
* @param hodnota
* hodnota, ktoru mame v plane vlozit
* @return index pola, kde by sa mala nachadzat zadana hodnota
*/
public static int binarneHladajIndex(int[] p, int odIdx, int poIdx, int hodnota) {
// Skontrolujeme korektnost indexov
if (odIdx > poIdx)
throw new RuntimeException("Parameter odIdx musi byt mensi alebo rovny ako poIdx.");
// Ak je hodnota vacsia, ako cislo na poslednom indexe uvazovaneho
// podpola, tak vratime nasledujuci index (spravne miesto pre hodnotu je
// az za poslednym prvkom podpola)
if (p[poIdx] < hodnota)
return poIdx + 1;
// Vieme, ze spravny index je medzi odIdx..poIdx - aplikujeme binarne
// vyhladavanie
while (odIdx < poIdx) {
// Vypocitame stredovy index
int stred = (odIdx + poIdx) / 2;
if (hodnota <= p[stred]) {
// Ak je hodnota mensia alebo rovna ako hodnota v strede, tak
// spravne miesto je niekde medzi odIdx..stred
poIdx = stred;
} else {
// Ak je hodnota vacsia ako hodnota v strede, tak spravne miesto
// bude az za stredovym indexom, t.j. niekde medzi stred+1 a
// poIdx
odIdx = stred + 1;
}
}
return odIdx;
}
/**
* Specialna verzia pre Adamov algoritmus, kedze on predpoklada, ze v poli
* ma prvky na indexoch 0..poIdx uz usporiadane.
*/
public static int binarneHladajIndex(int[] p, int poIdx, int hodnota) {
return binarneHladajIndex(p, 0, poIdx, hodnota);
}
/**
* Usporiada cisla v poli od najmensieho po najvacsie
*
* @param p
* pole, ktoreho prvky treba usporiadat
*/
public static void utried(int[] p) {
// Triediaci algoritmus na zaklade Adamovej myslienky
}
/**
* @param args
*/
public static void main(String[] args) {
int[] p = new int[30];
for (int i = 0; i < p.length; i++)
p[i] = (int) (Math.random() * 1000);
System.out.println(Arrays.toString(p));
utried(p); // AdamSort.utried(p);
System.out.println(Arrays.toString(p));
}
}