采用算法(顺序统计量)
发布时间
阅读量：
阅读量
选择算法（顺序统计量）
文章结构概览
- 算法选取（顺序统计量）
-
- 引入
- 期望在O(n)线性时间内完成的算法
- 分割处理步骤
- 算法选择过程
- 实验验证
- 参考文献
-
引入
在计算机科学领域，选择算法指的是用于从列表或数组中确定第k个最小元素的计算方法，该元素通常被定义为第k个顺序统计量。
通过应用排序算法，可以在O(n\log_2n)的时间复杂度内完成该问题的求解。然而，还存在一种更为高效的解决方案，其时间复杂度期望值为O(n)，能够在更短的时间内实现相同的目标。
期望为线性时间O(n)的算法
该算法与快速排序存在相似之处，均需要对输入的数组执行划分操作。然而，与快速排序递归处理划分后的两个子数组不同，本方法仅对其中一侧进行处理。因此，其期望时间复杂度为O(n)（具体取决于划分操作是否能够较为均衡地分割输入数组）。我们将这一算法命名为选择算法。
划分操作分析
该图示源自《算法导论》，其主要理念是将输入的数组划分为4个区域并分别实施处理。选取输入数组中的末尾元素作为基准值pivot。
还没有任何评论哟~