分治法

创建时间 2021-12-17

更新时间 2021-12-18

分类

计算机科学

标签

算法

找最大最小元素

问题：在元素表单独或同时找出第 $k$ 小元素

答：利用类似于快速排序的方式来求解：

随机选择一个 pivot
比它小的数放到左边
比它大的数放到右边
这样就知道了第 $k$ 小的数在那个组里
然后回到 1. 递归

复杂度分析

一般情况下，每次数组数量减半，那么：

第 1 趟的时间复杂度为 $O(n)$
第 2 趟的时间复杂度为 $O(n/2)$
…

于是：

$T(n) = n + {n \over 2} + {n \over 4} + \cdots = 2n = O(n)$

评论