首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >递归算法中考虑的比较次数

问递归算法中考虑的比较次数
EN

Stack Overflow用户
提问于 2014-03-09 14:11:26
回答 2查看 262关注 0票数 0

在(大多数)关于排序的研究论文中,作者得出结论,他们的算法采用n-1比较来对'n‘大小的数组(其中n是数组的大小)进行...so排序,因此当涉及到编码时,代码使用了比结论更多的比较。更具体地说,他们采用什么假设进行比较?

他们没有考虑到什么样的比较?

例如,如果您看一下冻结排序或增强插入排序。没有。在比较中,这些算法在实际代码中采用的比它们在图中指定的要多(没有。比较vs否。元素数量)

EN

回答 2

Stack Overflow用户

发布于 2014-03-09 16:38:36

在排序算法中完成的最小可能比较次数可以是n-1。在这种情况下,实际上根本不需要排序,而只是检查数据是否已经排序,本质上只是将每个元素与它之前和之后的元素直接进行比较(对于insertion sort来说,这是最好的情况)。很容易看出,比这更少的比较是不可能的,因为那样你就会有不止一个不相交的集合,这意味着你不会知道这些集合中的元素是如何相互比较的。

如果我们讨论的是平均/最坏情况,则所需的比较次数为Ω(n it's actually been proven n)。

递归或迭代的算法不会(直接)影响比较的次数。关于递归排序算法,我唯一能想到的就是递归深度。这在很大程度上取决于算法,但是quick-sort在n-1周围有一个(最坏情况)递归深度。

票数 1
EN

Stack Overflow用户

发布于 2014-03-09 16:22:16

  1. 更多的比较是分支的比较,这些比较在论文中经常被忽略,但在真实的代码中进行。(if (<stop clause>) return ...;),循环迭代器也是如此。
    • 它们通常被忽略的一个原因是,它们是在大小恒定的索引上完成的,而比较的元素(我们确实计算过)可能需要更多的时间,这取决于要比较的实际类型(对于example).

,字符串可能比整数需要更长的时间进行比较

​

  1. 还注意到,不能使用n-1比较(最差/平均情况)对数组进行排序,因为排序是Omega(nlogn)问题。然而,作者的意思可能是排序在算法的每一步都进行n-1比较,并且这些步骤可能有多个(通常是O(logn))。
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/22279064

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档