Dolní meze složitosti problému

  • Mějme nějakou složitost, nelze sestrojit algoritmus rychlejší než tato mez

  • Označujeme

  • Důkaz - najít takový hnusný vstup, kde algoritmus bude pomalý

  • V porovnávacím modelu RAM nelze třídit rychleji než pomocí porovnání

  • Naprosto zásadní výsledek informatiky

Druhy

  • Problém vyhledávání - v seřazené posloupnosti
  • Problém řazení - v neseřazené posloupnosti

Problém vyhledávání

  • V seřazené posloupnosti
    Definice

    Problém vyhledávání v porovnávacím modelu:

    • Vstupem algoritmu je číslo , vzestupně seřazená posloupnost čísel a hledané číslo
    • Úkolem algoritmu je zjistit, zda se vyskytuje v
Věta

Dolní mez složitosti problému vyhleádávní je operací porovnání
( = alespoň)

Důsledek

Pro každý korektní algoritmus vždycky existuje nějaký hnusný vstup () takový, že ten algoritmus provede alespoň operací

Problém řazení

  • V neseřazené posloupnosti
Definice

Problém řazení v porovnávacím modelu:

  • Vstupem algoritmu je číslo a posloupnost čísel
  • Výstupem je taková permutace vstupní posloupnosti , že platí
Věta

Dolní mez složitosti problému řazení je operací porovnání
( = alespoň)

Důsledek

Pro každý korektní algoritmus vždycky existuje nějaký hnusný vstup (vstupní permutace ) takový, že ten algoritmus provede alespoň porovnání

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25