teaching:ads12324_lecture
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revizePředchozí verze | |||
| teaching:ads12324_lecture [2024/05/24 14:16] – exam Martin Koutecky | teaching:ads12324_lecture [2024/05/29 20:41] (aktuální) – Martin Koutecky | ||
|---|---|---|---|
| Řádek 71: | Řádek 71: | ||
| * Integer multiplication using Karatsuba' | * Integer multiplication using Karatsuba' | ||
| * MomSelect (finding the $k$-th smallest element in an array in linear time) | * MomSelect (finding the $k$-th smallest element in an array in linear time) | ||
| - | * QuickSelect with random pivots works in expected $\mathcal{O}(\log n)$ time, QuickSort with random pivots in expected $\mathcal{O}(n \log n)$ time. | + | * QuickSelect with random pivots works in expected $\mathcal{O}(n)$ time, QuickSort with random pivots in expected $\mathcal{O}(n \log n)$ time. |
| * Edit Distance dynamic programming algorithm | * Edit Distance dynamic programming algorithm | ||
| * Longest Increasing Subsequence dynamic programming algorithm | * Longest Increasing Subsequence dynamic programming algorithm | ||
teaching/ads12324_lecture.1716553015.txt.gz · Poslední úprava: 2024/05/24 14:16 autor: Martin Koutecky