gpt4 book ai didi

algorithm - 最快的排序技术

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:09:59 25 4
gpt4 key购买 nike

这几天我一直在尝试各种排序算法。从...开始1) O(n^2) 时间复杂度排序的算法2) O(n log n) 时间复杂度与就地和异地排序技术

我想知道是否有任何排序算法可以在线性时间或更短时间内排序。我听说基数排序在最好的情况下接近线性时间排序,但具有一定的空间复杂性。谁能赐教一下?

最佳答案

您的排序永远不可能少于 O(N),因为您必须查看所有 N 个元素才能确定列表是否已排序 - 因此 O(N) 就在那里。如果您通过与列表中的其他元素进行比较进行排序,那么您的排序也不会比 O(NlogN) 更快 - 但如果您对数据有所了解,则可以。例如,如果您知道您的数据是英文字符串,则可以在排序之前将它们放入桶中。例如将所有以 A 开头的字符串放入一个桶中,将以 B 开头的字符串放入另一个桶中,依此类推。这会很快。不过,您可能需要使每个存储桶都相当大 - 也许大到足以容纳 1000 个字符串,因为并非所有存储桶都包含相同数量的字符串。

然后对各个桶进行排序,这样会很快。

对于数据的均匀分布(即 400 个以每个字母开头的字符串,当然你不会有),我估计这将是 O(N) + O(Nlog N/M),其中 M是桶的数量。

您显然可以为第二个字母设置嵌套桶,但是您拥有的桶越多,您的空间需求就越大,因为必须动态扩展桶会花费您的执行时间,因此您希望它们足够大以从...开始。这意味着它们中的许多将比它们需要的大很多,因为您并不了解有关数据分布的所有信息。

图书馆排序可能也值得一看。

关于algorithm - 最快的排序技术,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10604693/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com