分治
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| merge sort/mɜːdʒ sɔːt/ | 归并排序 | guī bìng pái xù |
| quicksort | 快速排序 | kuài sù pái xù |
分、解、合
- 归并排序 merge sort 对半分、递归、$\Theta(n)$ 合并：$T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$。快速排序 quicksort 把工作搬进划分——基准的好坏决定一切。
{exercise:uni-cs1002-skeleton}
练习
二分查找的递推式是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一次递归、常数合并：Θ(log n)。
快排三世界
- 均衡基准：$\Theta(n\log n)$。首元素基准遇有序输入：$T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$。
- 64 元课程数组实测：归并 310 次比较、快排 356、有序最坏 2080。随机基准期望 $2n\ln n \approx 1.39\,n\log_2 n$。
{exercise:uni-cs1002-quicksort}
练习
有序输入加首元素基准让快排花——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
T(n) = T(n−1) + n：每次划分只剥一个。
两个工作样例
- 最大子数组分治：左最优、右最优、或跨越中点的最优——跨越扫描整趟，$\Theta(n\log n)$。$[-2, 1, -3, 4, -1, 2, 1, -5, 4]$ 上答案是 6。
- 二分查找是退化情形：一次递归、常数合并，$\Theta(\log n)$——单枝仍是这个模式。
{exercise:uni-cs1002-subarray}
练习
[-2, 1, -3, 4, -1, 2, 1, -5, 4] 的最大子数组和为——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
段 4、−1、2、1 相加为 6。