66-Day3.md

第三节课小结

复杂度记号

$O(f)$是$f$函数最坏时间复杂度.

$\Omega(f)$是$f$函数最好时间复杂度.

$\Theta(f)$是$f$"大概"时间复杂度.

排序

快排

• 随机选择 pivot = x
• 将小于 A[x] 的放入 L, 大于放入 R
• 快排 L, R $\to$ L$^\prime$, R$\prime$
• 结合 L$^\prime$, A[x], R$^\prime$
• 时间复杂度 $O(n^2)$, 一般复杂度 $O(n\log(n))$

桶排

• 对于数，初始连续的桶。
• 将每个数放入对应的桶。
• 排好序了！
• $\Omega(n)$

数据结构

链表

二叉搜索树

2-3-4 数

• 类似二叉树，每个结点有2-4个.
• 从 root 到 leaf 的长度一样：平衡
• 最差长度：$\lg(n)$
• 搜索和插入：$O(\log(n))$

红黑树

• 将2,3-结点拆分为红 edge.
• 通过旋转达到平衡.
• 最长长度：$2\lg(n+1)$.
• 搜索和插入：$O(\log(n))$