Užitečné vědět
•  Vstupní podmínka A Inicializace =>• Invariant Invariant A Průchod cyklem =>• Invariant
Invariant A Negace podmínky cyklu =>• Výstupní podmínka
•  Invariant je něco jiného, než podmínka cyklu
•  Invariant má 2 části. Jedna se vztahuje k myšlence algoritmu a výstupní podmínce, druhá k podmínce cyklu.
•  Nespleťte rozsah invariantu - algoritmus se vrátí na dané místo, aby ověřil podmínku cyklu, i když do samotného cyklu již nevstoupí
•  Invariant se obvykle dokazuje indukcí podle počtu průchodů cyklem.
•  Pokud něco dokazujete indukcí, je dobré přehledně uvést následující:
—  co dokazujete
—  podle čeho indukci vedete
—  bázový krok, indukční předpoklad a indukční krok
•  Indukce pro funkce na stromech se vede podle hloubky stromu. Většinou se aplikuje nějaká operace na kořen a funkce se pak zavolá na jednotlivé podstromy, které již mají délku o 1 nižší.
•  Indukce na seznamech se vede podle počtu prvků daného seznamu.
•  6 < log log n < log n < log    n < n < log n! = n log n < n2 = n2 + log n <
7n5 - n3 + n < (§)" < 2™ < n! < n™
•  Časová složitost
—  bubblesort O (n2)
—  heapsort Q (n ■ log n)
—  insertsort O (n2)
—  mergesort O (n • log n)
—  quicksort O (n2)
—  selectsort O (n2)
1