在(大多数)关于排序的研究论文中,作者得出结论,他们的算法采用n-1比较来对'n‘大小的数组(其中n是数组的大小)进行...so排序,因此当涉及到编码时,代码使用了比结论更多的比较。更具体地说,他们采用什么假设进行比较?
他们没有考虑到什么样的比较?
例如,如果您看一下冻结排序或增强插入排序。没有。在比较中,这些算法在实际代码中采用的比它们在图中指定的要多(没有。比较vs否。元素数量)
发布于 2014-03-09 16:38:36
在排序算法中完成的最小可能比较次数可以是n-1。在这种情况下,实际上根本不需要排序,而只是检查数据是否已经排序,本质上只是将每个元素与它之前和之后的元素直接进行比较(对于insertion sort来说,这是最好的情况)。很容易看出,比这更少的比较是不可能的,因为那样你就会有不止一个不相交的集合,这意味着你不会知道这些集合中的元素是如何相互比较的。
如果我们讨论的是平均/最坏情况,则所需的比较次数为Ω(n it's actually been proven n)。
递归或迭代的算法不会(直接)影响比较的次数。关于递归排序算法,我唯一能想到的就是递归深度。这在很大程度上取决于算法,但是quick-sort在n-1周围有一个(最坏情况)递归深度。
发布于 2014-03-09 16:22:16
if (<stop clause>) return ...;),循环迭代器也是如此。,字符串可能比整数需要更长的时间进行比较
n-1比较(最差/平均情况)对数组进行排序,因为排序是Omega(nlogn)问题。然而,作者的意思可能是排序在算法的每一步都进行n-1比较,并且这些步骤可能有多个(通常是O(logn))。https://stackoverflow.com/questions/22279064
复制相似问题