Programování IV.

Třídící algoritmy

• máme data, která se dají nějak porovnávat (větší menší rovná se)
• chceme dosáhnout toho, aby tvořili rostoucí nebo klesající posloupnost
• lépe se v tom pak hledá, může to zjednodušit řešení jiných problémů
• algoritmy
  • selection sort $O(N^2)$
  • bubble sort $O(N^2)$
  • merge sort $O(N \log N)$
    • paměťově složitý
  • quick sort $O(N \log N)$
• vlastnosti algoritmů
  • stabilita
  • in-place třízení
  • rychlost
  • paměťová náročnost

Rekurze

• funkce volá ve své definici někde sama sebe
• dělení
  • přímá - volá se přímo
  • nepřímá - volá se nepřímo přes jiné funkce
• dělení
  • lineární rekurze
    • zavolá se pouze jednou
  • stromová rekurze
    • zavolá se vícekrát
• příklady
  • fibbonaci
  • faktoriál

Složitost

• asymtotická složitost
• notace velké O
• zanedbáváme konstanty
• vyjadřuje složitost běhu algoritmu vzhledem k velikosti vstupu
• příklad
  • $O(N^2)$