我想得到的理论原因不是实验结果.另外,我们如何确定数据大小何时被调用为小或大？
我没有解释清楚,我的意思是当输入数据大小很小时,我们通常选择使用插入排序或不使用快速排序,这是正确的.所以我想知道为什么会这样？
Jim*_*hel 14
请记住,在渐近分析中,我们忽略了常数因子.因此Quicksort的O(n log n)复杂度实际上是O(C(n log n)),其中C是一些未知常数.类似地,插入排序的O(n ^ 2)实际上是O(C(n ^ 2)).我们称这些常数为Cq和Ci.
因此,当(Ci*n ^ 2)<(Cq*(n log n))时,插入排序会更快.
从Ci <Cq这两个算法看,应该是显而易见的.插入排序非常简单.算法只是比较和交换,抛出一点循环开销.
Quicksort有点复杂,每次迭代需要更多步骤,但迭代次数更少.
考虑对五元素数组进行排序.插入排序最好:
现在看看Quicksort,它在一般情况下必须分区四个子阵列.5元素数组被分成两个3和2个元素的子数组.将3元素子阵列进一步划分为1和2个元素的子阵列.然后分割两个2元素子阵列.
因此该partition方法将被调用四次.除了元素的比较和交换以及其他开销之外,每个分区步骤至少需要两次交换.当你全部添加它时,你会看到Quicksort每次迭代都会做更多的工作.当迭代次数很少时,即使进行更多迭代,插入排序也会减少总工作量.
您可以进行逐步分析以确定"小"的理论值,其中插入排序将比Quicksort快.通常这是通过计算"基本操作"来完成的,尽管定义有些灵活.在这种情况下,它非常简单:比较,赋值或函数调用是"基本操作".
理论结果如何与实验得出的结果相匹配将取决于特定的计算机硬件以及有多昂贵的比较.如果比较非常昂贵,那么您将需要选择执行最少数量比较的算法.但是,如果比较相对便宜(例如,比较数字,或者甚至是字符串,只要它们没有长公共前缀),那么算法开销就是限制因素,简单的低效算法优于复杂的高效算法.
| 归档时间： |
|
| 查看次数： |
3130 次 |
| 最近记录： |