Please enable JavaScript.

Coggle requires JavaScript to display documents.

18. Rekurzivní algoritmy (Metoda rozděl a panuj (výhody (efektivnost…

- - - - pomalá
      - někdy příliš komplikovaná
      - podproblémy na zásobník (stack overflow)
    - - možná nerekurzivní implementace (podproblémy do datové strukt. - zásobník, fronta, prioritní fronta)
      - umožňuje měnit pořadí podproblémů
- - - - --> cyklus
      - rekurze - velmi pomalé (fib(i-1) + fib(i-2)
      - odstranění - dynamické programování - ukládání vypočítaných hodnot
    - - rekurze: number*fac(number-1)
      - cyklus: for(int i = number; i > 1; i--) result = result*i
- - - - předpoklad: splněno následující
      - základní krok V(n0) platí
      - n0 z Z, V(n) - vlastnost celých čísel, která má smysl pro n>=n0
      - indukční krok - pro každé n z Z, n>=n0 je pravdivá implikace:
      - jestliže platí V(n), pak platí V(n+1)
      - potom V(n) platí pro všechna n z Z, n>=n0
  - - - krok dolů
      - víme, že alg. vyřeší problém V(n) a ptáme se, jestli vyřeší i podproblémy V(n+1)
    - - krok nahoru
      - známe V(n), ptáme se, jestli pomocí ní zvládneme i V(n+1)
- - - - na jednu stranu menší, na 2. větší
      - rekurzivně opakujeme
      - zvolíme pivota
    - - náhodný prvek
      - ideálně - 2 poloviny - O(n log n)
      - medián 1., prostředního a posledního
      - fixní prvek (ne - seřazené pole)
  - - - v každém kroku zvolíme prostřední prvek + porovnáme s x
      - 2b. totožné - vrátím index, menší - doleva, větší - dorpava
      - seřazené pole
      - rekurzivně zavoláme na danou polovinu pole
  - - - pole půleno - rekurzivně - triviální seřazení
      - postupně setřiďujeme prvky do větších a větších polí
      - v každém okam. vybereme ze 2 sousedních seznamů 2 prvky - vybereme vyšší - nakopírujeme do pole vyšší úrovně
- - - - tvoří se kruh volání
    - - podprogram volá sám sebe