ZAX*_*ZAX 6 sorting algorithm big-o radix-sort bucket-sort
我正在探索以下算法:
我知道这三个都能够在最佳情况下以线性时间运行,但是我很难理解这些情况何时发生,除了计算排序的情况.
以下是我对计数排序的理解,以及如果可能的话我希望如何回答其他两种算法:
当您希望排序的信息之间没有大的间隙时,计数排序以线性时间运行.例如,1,10 ^ 5和545等将创建一个大型数组并且使用内存和遍历效率不高所以这将是使用计数排序的"更糟糕的情况",因此最好的情况是差距很小.
如果有人能帮我理解线性时间发生时基数和桶排序最佳情况的条件,我将不胜感激.
让我们从独立分析每个算法开始,看看我们是否可以确定它们将在线性时间内运行的情况.
首先,让我们看一下排序计数.算法的工作原理如下:
第一步可以通过迭代主阵列在时间O(n)中完成.让我们假设数组中的最大值是U.在这种情况下,第二步需要时间O(U),因为我们必须将数组元素清零.第三步需要时间O(n).然后最后一步花费时间O(n + U),因为我们只访问频率数组的每个元素一次(O(U))并且总共n次写入输出数组O(n).这意味着总运行时间为O(n + U).请注意,这取决于需要排序的元素总数(较大的数组需要更长的排序时间)和数组中元素的大小(较大的数字将需要按比例增加运行时间).
如果我们希望这个运行时为O(n),我们需要要求U = O(n).这样,我们就会得到O(n + U)= O(n + n)= O(n).这意味着您需要使阵列中最大元素的大小以与阵列长度增加的速率大致相同的速度增长.例如,如果您确保数组中的所有元素都在1 .. n范围内,则计算排序将需要时间O(n)才能完成.这些元素如何在该范围内分布并不重要.
基数排序基本上是通过反复对计数排序反复进行,对阵列中数字的每个数字进行一次排序.基数排序背后的关键思想是保持U值与之前算法的值尽可能低.通过选择一些固定的基数,U的值被限制在某个常数.例如,如果您使用二进制基数排序并一次一位,则要排序的数组的每个元素基本上被视为0或1.这意味着每轮基数排序需要时间O( n)完成.然后,对整个阵列进行排序所需的轮数由数组中最大数字的位数给出,即Θ(log U).这意味着算法的总运行时间最终为O(n log U).再次注意,运行时取决于元素的数量和数组中最大元素的大小.
这次的优点是log U比U长得多,慢得多.例如,2 300大约是宇宙中的原子总数,但是lg(2 300)= 300,这是非常小的.
有些人会声称log U是任何固定计算机上的常量.在32位计算机上,所有整数都是32位(除非您使用的是任意精度整数库,我们现在将忽略它),而在64位系统上,所有整数都是64位.在第一种情况下,log U = 32,在第二个日志中U = 64.您可以声称对于固定系统,基数排序总是需要线性时间,因为运行时将是O(n).但是,常数因系统而异.如果你在理论上更有想法并希望更精确,你可以说基数排序在线性时间内运行,只要log U = O(1),因为那样O(n log U)= O(n).这意味着如果您对数字中的位数有任何常量上限,则可以保证基数排序将以线性时间运行.
桶排序算法类似于基数排序,除了它使用最高有效数字而不是最低有效数字来分配元素.这意味着分析与以前几乎相同 - 只要log U = O(1),算法就会以线性时间运行.
希望这可以帮助!