分治法
找最大最小元素
问题：在元素表单独或同时找出第 k 小元素
答：利用类似于快速排序的方式来求解：
- 随机选择一个 pivot
- 比它小的数放到左边
- 比它大的数放到右边
- 这样就知道了第 k 小的数在那个组里
- 然后回到 1. 递归
复杂度分析
一般情况下，每次数组数量减半，那么：
- 第 1 趟的时间复杂度为 O(n)
- 第 2 趟的时间复杂度为 O(n/2)
- …
于是：
T(n) = n + {n \over 2} + {n \over 4} + \cdots = 2n = O(n)
问题：在元素表单独或同时找出第 k 小元素
答：利用类似于快速排序的方式来求解：
一般情况下，每次数组数量减半，那么：
于是：
Comments