Prezentacia - Vypoctova zlozitost algoritmov 26.10.2020 9:15

Zhrnutie prednášky

Prednáška nadväzuje na problém triedenia ako ukážku toho, že jeden problém možno riešiť algoritmami s rôznou výpočtovou zložitosťou. Zopakovala sa bublinová metóda, ktorej počet výmen sa rovná počtu inverzií a v najhoršom prípade má zložitosť Θ(n²), pričom varianty (prebublávanie maxima, minima, pretriasanie) počet výmen nemenia. Hlavná časť sa venuje quicksortu, ktorý využíva metódu rozdeľuj a panuj: výber pivota, rozdelenie poľa na menšie a väčšie prvky, rekurzívne utriedenie častí a triviálne zloženie výsledku. Vysvetlené je, že ideálnym pivotom by bol medián, no jeho nájdenie je rovnako náročné ako samotné triedenie. Na záver sa podrobne rozoberá variant s pivotom na prvej pozícii a rozdelením cez for cyklus, vrátane invariantu cyklu s indexmi i a j.

• - Triedenie ukazuje, že jeden problém možno riešiť algoritmami s rôznou zložitosťou.
• - Bublinové triedenie a quicksort sú vnútorné triedenia výmenou na mieste, s konštantným počtom pomocných premenných.
• - Počet výmen v bublinovom triedení sa rovná počtu inverzií; najhorší prípad je Θ(n²), varianty to nemenia.
• - Výmena susedných prvkov zníži počet inverzií iba o jednu, preto quicksort vymieňa vzdialenejšie prvky.
• - Quicksort používa metódu rozdeľuj a panuj: výber pivota, rozdelenie na menšie a väčšie prvky, rekurzia, triviálne zloženie.
• - Medián je ideálny pivot, ale jeho nájdenie je rovnako ťažké ako triedenie, preto je výber pivota v praxi viac-menej jedno.
• - Invariant cyklu je tvrdenie platné na začiatku každého cyklu; pri rozdeľovaní oddeľuje úsek prvkov menších ako pivot, úsek väčších alebo rovných a ešte neprejdenú časť.

Zhrnutie pripravené s pomocou AI z prepisu videa.