tem*_*def 23 sorting algorithm complexity-theory
在最近的一个周六早餐早餐谷歌漫画中,作者描述了一种名为Frog Sort的算法,用于对自然数列表进行排序.这个算法在漫画中有描述,但为了简单起见,我在这里重印了它:
该算法假设所有青蛙都以相同的速度吃苍蝇.结果,从它的盒子里跳出来的第一只青蛙将是每只苍蝇数量最少的青蛙,第二只青蛙是第二只吃最多的苍蝇,等等.
在漫画的中间,老师问学生"什么是最大步数？",我解释为"这个算法终止所需的最大步数是多少？" 也就是说,算法的运行时间是多少？然后学生回答"log frog(盒子)".
这是对该算法运行时的准确分析吗？或者作者错了？
小智 12
这种运行时分析显然是错误的; 我们可以获得一个简单的Ω运行时max(n_elements, largest_element)(因为我们已经制作了n_elements盒子,然后每个盒子的内容与其内容的大小一样长).一个不到n次的排序算法将是......非常令人惊讶.
如果你想在互联网上找到更多的分析,这个算法相当于sleep-sort.如果你不熟悉那个荒谬的算法,这里是bash:
#!/bin/bash
function sort() {
for num in "$@" ; do
(
sleep $num
echo $num
) &
done
wait
}
sort 6 1 3 4
我很确定漫画的作者是错的.下面是对该算法的更正式的分析.
首先,我们需要为青蛙如何食用苍蝇制定一些基本规则.我会假设所有的青蛙都能以恒定的速度吃蝇.也就是说,一只青蛙吃一只苍蝇需要r秒,青蛙吃十只苍蝇需要10秒钟等等.接下来,我们做出(合理的)假设所有的青蛙都在平行进食.我们还假设一只青蛙跳出一个空盒子需要j时间.
我们还需要考虑设置时间.让我们假设我们手头有无限量供应的苍蝇,青蛙和盒子,让我们说它需要一点时间才能得到一个盒子和时间将一只苍蝇放入一个盒子里.最后,我们假设将青蛙放入盒子需要花费很多时间.为简单起见,我们假设青蛙在我们明确指示它们之前不会开始吃苍蝇,这样青蛙就会在其他青蛙没有开始之前放入盒子里.
最后一个细节 - 让我们假设需要花时间写下一个数字.
在这种情况下,该算法的运行时间如下.假设我们要排序的数字列表是x 1,x 2,...,x n.在这种情况下,所需的时间量来设置所有框将为n(B + F)+ Y(ΣX 我).这样做的原因是我们需要得到n个盒子并将一只青蛙放入每个盒子(因此是第一个术语),加上每个苍蝇的y单位时间(因此是第二个术语).
在算法过程中,当青蛙跳出盒子时,我们需要将每个数字写下一次.这意味着在整个算法中,我们将完成写下排序序列的工作.
最后,我们必须考虑所有青蛙完成所需的时间.由于所有的青蛙都在平行进食,我们需要关心的只是吃苍蝇最多的青蛙.这只青蛙将有x max苍蝇吃,其中x max是输入列表中的最大数量.因此,青蛙进食的时间由rx max给出.考虑到最终青蛙的跳跃,青蛙,所有并行工作,将在rx max + j时间内共同完成.
这意味着算法的总时间由下式给出
N(F + B)+yΣx 我 + NW + RX 最大 + J.
如果我们现在假设"一个工作单元"就足够做任何单个操作(有青蛙吃苍蝇,或跳出盒子,或者把一个青蛙在一个盒子里,等),总所需时间最多
n +Σ(x i)+ x max + 1
他指出,X 最大 ≤ΣX 我,我们得到了该算法的总运行时间为Θ(N +σX 我).换句话说,运行时与要排序的数字和要排序的数字的总大小成比例.
请注意,此运行时中没有任何对数,因此我们可以立即断定作者的运行时分析不正确.
最后,请注意这是一个非常糟糕的排序算法.所述计数排序算法可以排序n的时间为O(n + U),其中U是要排序的最大值,这是渐近比FrogSort更好的自然数.该基数排序算法可以为O做到这一点(N LG U)的时间,这对于美国的大的价值,进一步话又说回来,这两种算法需要复杂的机械,它可能不会在由漫画所描述的设置存在.
希望这可以帮助!