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