《算法导论的Java实现》 10 中位数和顺序统计学
16lz
2021-01-22
10 中位数和顺序统计学
10.1 最大元素和最小元素
伪代码:
Java代码:
输出:
26
code后感
这可能是《算法导论》里面最简单的程序之一。但是《算法导论》一书的最大特点就是,算法本身不难,或者说,像我现在这样的工作:把伪代码用某种具体语言去实现一遍,是非常容易的事儿。
但是算法的分析,却绝不简单。比如,要证明MINIMUM算法是最优的;再比如,去分析伪代码的第4行,赋值次数的期望值,都是不太容易的事儿。对于普通的程序员来说,也许未必就一定要掌握这些,只要记住一些结论也就可以了————第4行被执行的期望值是Θ(lg n)。
10.2 以线性期望时间做选择
伪代码:
Java代码:
输出:
41
code后感
我有点晕: 快速排序的随机化版本的函数RANDOMIZED-PARTITION居然可以用在这里。用线性时间得到数组里面的最大或者最小值,实在是一个小学生都会做的事儿————一个一个比较就可以了。
但是,用线性时间得到数组第N大的值,就不那么容易了。《算法导论》里面说,“一般选择性问题看起来要比寻求最小元问题跟难些。但是令人惊奇的是,两个问题的渐近时间是一样的:都是Θ(n)”。
这真的很令人惊奇,可以想象一下,让一个小学生去从10个数字里面选出第3小的那个。他会怎么做呢?小学生也许会先找到最小的,再找到次小的,最后找到第3小的那个。
如果这样,那么算法复杂度肯定是n的二次方了。
RANDOMIZED-SELECT的神奇之处在于它的渐近时间居然是Θ(n)!
更多相关文章
- JAVA 关于图片上传的代码
- 线程“main”中的异常java.lang.RuntimeException:无法编译的源代
- java 和 C 代码运行效率的比较(整理)
- 基于内容估计文本宽度的算法
- Java:IntelliJ想法生成的代码错误地为所有Class名称添加了其包名
- 算法竞赛入门经典(分数化小数)
- 关于几个位运算的算法分析
- 求一段与读取数据库数据,写入一个数组的javascript 代码!谢谢!!
- java动态编译 (java在线执行代码后端实现原理)