AGe*_*eek 4 c algorithm
使用数据结构自平衡二进制搜索树查找数组中第n个最小/最大元素的算法
阅读帖子:以最佳方式在二叉搜索树中查找第k个最小元素.但正确的答案并不清楚,因为我无法弄清楚正确的答案,我拿了一个例子......请多说明一点......
Jer*_*fin 13
CAR Hoare的select算法就是为了这个目的而设计的.它在[预期]线性时间内执行,具有对数额外存储.
select
编辑:排序的明显替代方案,然后选择正确的元素具有O(N log N)复杂度而不是O(N).i以排序顺序存储最大元素需要O(i)辅助存储,并且大致为O(N*i log i)复杂度.如果先验已知非常小(例如1或2),则这可以是胜利.对于更一般的用途,通常更好.iselect
i
编辑2:随便,我没有一个很好的参考,但在前一个答案中描述了这个想法.
归档时间：
15 年，10 月 前
查看次数：
1241 次
最近记录：
14 年，1 月 前