Algoritmy a dátové štruktúry prednáška 03

Zhrnutie prednášky

Prednáška najskôr spresňuje pojem veľkosti vstupu a ukazuje na príklade naivného testovania prvočíselnosti, že algoritmus, ktorý sa javí ako lineárny vzhľadom na hodnotu čísla N, je v skutočnosti exponenciálny vzhľadom na počet cifier N, čo súvisí aj s praktickou dôležitosťou tejto problematiky v kryptografii. Ďalej sa podrobne rozoberá algoritmus Merge sort vrátane implementácie funkcie merge (lineárna zložitosť O(a+b)) a analýzy celkovej zložitosti pomocou stromu rekurzie, ktorá vedie k výsledku Θ(n log n). Následne sa predstavuje takzvaný Stooge sort, ktorý pole rozdeľuje na tri prekrývajúce sa dvojtretinové časti a rekurzívne ich triedi v poradí prvá-druhá-prvá časť; dokazuje sa jeho korektnosť aj časová zložitosť n na logaritmus so základom 3/2 z čísla 3, teda približne n na 2,71. Na záver sa porovnávajú obe riešenia - Merge sort s n log n je výrazne efektívnejší ako Stooge sort - a zdôrazňuje sa výhodnosť logaritmickej zložitosti oproti kvadratickým algoritmom ako bubble sort či insertion sort.

• Formálna definícia veľkosti vstupu (bity/cifry vs. hodnota čísla)
• Testovanie prvočíselnosti - lineárne vs. exponenciálne v počte cifier
• Kryptografická relevancia (faktorizácia, RSA)
• Implementácia a zložitosť funkcie merge O(a+b)
• Merge sort - analýza cez strom rekurzie, Θ(n log n)
• Stooge sort - delenie na tri prekrývajúce sa dvojtretinové časti
• Dôkaz korektnosti a zložitosť Stooge sortu n^log(3/2)(3) ≈ n^2,71
• Porovnanie n log n s kvadratickými algoritmami

Zhrnutie pripravené s pomocou AI z prepisu videa.