用O(nlgk)时间查找k分位数 2014-03-17

相关问题： The kth quantiles of an n-element set are the k 1 order satatistics that divide the sorted set into k equal-sized sets(to ...

(877)次阅读|(0)个评论

找出集合S最接近中位数的k(k≤n)个数 2014-03-17

相关问题： 给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k≤n后，它能确定出S中最接近其中位数的k个数. 思考过程： 如果 ...

(959)次阅读|(0)个评论

最坏情况快速排序的运行时间为Ο(nlgn)的算法 2014-03-14

思想方法与思考过程： 快速排序对主元的划分决定了其运行时间，如果最坏是Ο(nlgn)，那么就不允许出现极端划分情况。因为我们学习了最坏时间了线性的选择 ...

(875)次阅读|(0)个评论

最坏为线性时间的查找第i小元素 2014-03-14

思想方法： 既然是线性时间查找元素，那么我们每次划分时都需要均衡划分。所以我们每次总是取中位数辅助数组B的中位数x为原数组A的主元进行划分。 该 ...

(894)次阅读|(0)个评论

算法导论第九章课后答案 2014-02-06

9.1-1 证明：在最坏情况下，找到n个元素中第二小的元素需要n+向上取整lgn-2次比较。 我们对于查找第2小元素分成2步。 step1:我们先将数组中的元素两两成对 ...

(4705)次阅读|(0)个评论

算法导论第八章思考题 2014-01-27

8-1(比较排序的概率下界) 在这一问题中，我们将证明对于给定的n个互异的输入元素，任何确定或随机的比较排序算法，其概率运行时间都有下界Ω(nlgn)。首先分析 ...

(2307)次阅读|(0)个评论

查看更多