算法导论里的一个问题。

bida33755 2010-08-07 05:50:02

在合并排序中对小数组采用插入排序。
注：书里的那个O里还有一杠的符号打不出来，所以这里用大O代替了，特指同阶无穷大量。

尽管合并排序最坏情况运行时间为O(nlgn)，插入排序的最坏运行时间为O(n^2)，但是插入排序的常数因子使得它在n较小时，运行要更快一些。因此，在合并排序算法中，当子问题足够小时，采用插入排序就比较合适了。考虑对合并排序做这样的修改，即采用插入排序策略，对n/k 个长度为 k 的子列表进行排序。然后，再用标准的合并机制将它们合并起来，此处k是一个待定的值。

a) 证明在最坏的情况下，n/k个子列表可以用插入排序在O(nk)的时间内完成排序

b) 证明这些子列表可以在O(nlg(n/k))最坏情况内完成合并。

c) 如果已知修改后的合并排序算法的最坏运行时间为O(nk+nlg(n/k)),要使得修改后的算法具有与标准合并算法一样的渐进运行时间，k的最大渐进值( 即O形式）是什么（以n的函数形式表示）？

d) 实践中，应该如何选取k值。
---------------------------------------------------------------------------------
主要是后两个的问题。关于k的表示。
我的解答是:

T(n) = O(k^2) n = k 时
T(n) = 2T(k/2) + O(n)
经过归纳证明，我得出 T(n) = (n/k) * T(k) + lg(n/k) * O(n) = O(nk + nlg(n/k))
接下来
(nk + nlg(n/k)) / nlgn --> C (常量) ( n --> infinite )
k - lgk = O(lgn)
到这里，我就不知道k该取什么了, 看起来似乎与lgn同阶的样子，谁能给个严格而又详细的解答？谢谢！

...全文

511 24 打赏收藏转发到动态举报

写回复

用AI写文章

24 条回复

切换为时间正序

请发表友善的回复…

发表回复

bida33755 2010-08-08

打赏
举报

常量因子的倍数关系不好处理，取决于实现（比较，复制以及动态内存分配释放），不过于我的机器，经过实际测试，基本上可以确定k的取值在60以内时性能不会有明显变化，差距在毫秒级。一亿时 lgn 恰好处于此范围。

花了近一天研究这个问题，勉强解决了一些疑问，虽然性能上有1倍的优势，但还是觉得不值。学习下一章中。
结贴！

bida33755 2010-08-08

打赏
举报

呃，是本书配套的答案册。

bida33755 2010-08-08

打赏
举报

不错，k选lgn的并不是很通用，若要准确的取值，需比较在小n下两种算法执行步骤的具体表达式。

题号是 2-1
我从官方找过答案，没有这一题。

r11222 2010-08-07

打赏
举报

同时我想问楼主你这题的题号是多少，我以前看过一个完整答案，想找出来

r11222 2010-08-07

打赏
举报

K选lgN 表面上保证不比nlgn大，但这个保证是在你把0（）号去掉的情况，而，实际中 0（nlgn）！=nlgn

r11222 2010-08-07

打赏
举报

In theory, we want to pick k so that the running time does not exceed O(n lg n) expected running time of
quicksort. In practice, we can pick k between 1 and lg n by running experiments.

你不可能永远选lgn作为K, 因为 n很大的时候，lgn 也很大。用插入排序对这k个元素进行排序就很慢了

michael122 2010-08-07

打赏
举报

c) k当然最大只能去lgn了，使得kn不超过nlogn，因为后面一项不会超过nlgn
d) 题意说 nk前面的系数小，nlg(n/k)前面的系数大，当n比较小的时候，选取k适当的大一点（可以比lgn大一些），n比较大的时候，选取k小一点(lgn)

bida33755 2010-08-07

打赏
举报

测试过linux下的qsort实现了，效率与std::sort差距不大，慢了两到三秒的样子。
顺便提一下freebsd下的qsort与mergesort实现，在本例下一亿级时快得简直不可思议，前者4.79,后者3.98，应是对最坏情况做了特殊处理，否则没有这么的。。。唔，BT

jackyjkchen 2010-08-07

打赏
举报

[Quote=引用 15 楼 bida33755 的回复:]
引用 13 楼 jackyjkchen 的回复:

real、user、sys……你不是Windows吧，Windows现在不支持real模式了

另外建议再看看C运行库快排qsort的情况，他也是用插入优化的，最好将源码拉出来编译，比直接调用CRT要快

是用linux的time命令计算的，real 是指实际运行时间，其值为用户级调用user+内核级调用sys。
qsort吗，……
[/Quote]
哦，我将real理解成类似于dos的那种“实模式”了

bida33755 2010-08-07

打赏
举报

[Quote=引用 13 楼 jackyjkchen 的回复:]

real、user、sys……你不是Windows吧，Windows现在不支持real模式了

另外建议再看看C运行库快排qsort的情况，他也是用插入优化的，最好将源码拉出来编译，比直接调用CRT要快
[/Quote]

是用linux的time命令计算的，real 是指实际运行时间，其值为用户级调用user+内核级调用sys。
qsort吗，汗一个，从来没有用过的函数，现在研究一下。

bida33755 2010-08-07

打赏
举报

不知道大家对性能提高是否还有建议，再顶！有谁测试过常量级空间复杂度合并排序的性能？

jackyjkchen 2010-08-07

打赏
举报

real、user、sys……你不是Windows吧，Windows现在不支持real模式了

另外建议再看看C运行库快排qsort的情况，他也是用插入优化的，最好将源码拉出来编译，比直接调用CRT要快

bida33755 2010-08-07

打赏
举报

[Quote=引用 8 楼 cattycat 的回复:]

第一个O(n/k*k^2)=O(nk).这里的O中间有一横
第二个n/k个列表两两合并，合并完继续合并，共lg(n/k)对，合并的代价O(n).所以O(nlg(n/k)).
第三个O(nk+nlg(n/k))=O(nlgn).只能最大是k=O(lgn).等式左边中第一项是高阶项。k如果大于lgn,则比归并排序复杂度大了。左边可以写成nk+nlgn-nlgk，k等于lgn时，就是2nlgn-n……
[/Quote]

不错，解决了我第三题的问题。第四个k比较伤脑筋，看起来要详细比较常量因子与低阶项，不过上面测试似乎
已经表明最佳的k值与lgn非常接近了。

jackyjkchen 2010-08-07

打赏
举报

你测试的是最坏情况？我测试的是随机数据，区别可能就在于此。

在随机条件下，std::sort应该比std::stable_sort快

bida33755 2010-08-07

打赏
举报

没有缩进，再发下：



一亿级输入规模：

  time(s)                merge_insertion_sort                    merge_sort                 std::sort            std::stable_sort

  real                      17.96                                              33.76                            25.06                18.67

  user                      13.58                                             29.61                            24.62                18.02

  sys                        4.36                                                4.13                              0.42                  0.63



一千万级输入规模

                                1.46                                               3.07                              2.24                  1.69

                                1.17                                                2.79                             2.19                  1.63

                                0.28                                                0.27                              0.05                0.06

bida33755 2010-08-07

打赏
举报

刚才以 k = lgn 做了测试，发现结果还是比较乐观的，在最坏情况下改良的合并排序比正统的实现快一倍！下面是测试结果，同时与 std::sort , std::stable_sort进行了比较。输入序列是特别准备的逆序数组。

一亿级输入规模：
time(s) merge_insertion_sort merge_sort std::sort std::stable_sort
real 17.96 33.76 25.06 18.67
user 13.58 29.61 24.62 18.02
sys 4.36 4.13 0.42 0.63

一千万级输入规模
1.46 3.07 2.24 1.69
1.17 2.79 2.19 1.63
0.28 0.27 0.05 0.06

只有在千万级以上的输入规模时能看出明显的优势，增大k的常量因子时将变慢，没有测试过比1小的因子，不
过看其与std::stable_sort的接近程度，应该趋于最佳了。性能瓶颈是系统调用时间，可能是由于n级的空间复杂
度导致大量的动态内存分配释放，从而增加开销。不知一次分配大内存然后自管理是否会有改善。
对于k取lgn还是没有一个严格的理论证明。自己顶！

cattycat 2010-08-07

打赏
举报

第一个O(n/k*k^2)=O(nk).这里的O中间有一横
第二个n/k个列表两两合并，合并完继续合并，共lg(n/k)对，合并的代价O(n).所以O(nlg(n/k)).
第三个O(nk+nlg(n/k))=O(nlgn).只能最大是k=O(lgn).等式左边中第一项是高阶项。k如果大于lgn,则比归并排序复杂度大了。左边可以写成nk+nlgn-nlgk，k等于lgn时，就是2nlgn-nlglgn.与归并排序是一样的。
第四个k应当是最大的列表长度，这个长度上插入排序要比合并排序快。