algorithm - Saturday Morning Breakfast Cereal 中 FrogSort 的分析是否正确？

Question

在 recent Saturday Morning Breakfast Cereal comic ，作者描述了一种称为 Frog Sort 的算法，用于对自然数列表进行排序。该算法在漫画中有所描述，但为了简单起见，我在此处转载了它:

1. 对于每个要排序的自然数，制作一个盒子，里面放着那么多苍蝇。
2. 在每个盒子里放一只 Frog 。
3. 虽然还不是所有的 Frog 都跳出盒子:
   1. 等待 Frog 跳出盒子。
   2. 写下最初放在盒子里的苍蝇的数量。
4. 生成的数字序列是原始数字列表，但按排序顺序排列。

该算法假设所有 Frog 以相同的速度吃苍蝇。结果，第一只跳出盒子的 Frog 将是每只 Frog 吃的苍蝇数量最少的 Frog ，第二只 Frog 则是吃掉的苍蝇数量第二少的 Frog ，依此类推。

在漫画的中间，一位老师问学生“最大步数是多少？”，我将其解释为“此算法终止所需的最大步数是多少？；”也就是说，算法的运行时间是多少？然后学生回答“log_frog(boxes)”。

这是对该算法运行时间的准确分析吗？还是作者错了？

Answer 1

这个运行时分析显然是错误的；我们可以获得 max(n_elements, largest_element) 的微不足道的 Ω 运行时间(因为我们已经制作了 n_elements 框，然后每个框的清空时间与其大小一样长内容)。花费少于 n 时间的排序算法会......非常令人惊讶。

如果你想在网上的某个地方找到更多的分析，这个算法相当于 sleep 排序。如果你不熟悉那个荒谬的算法，这里是 bash:

#!/bin/bash

function sort() {
    for num in "$@" ; do
        (
        sleep $num
        echo $num
        ) &
    done
    wait
}

sort 6 1 3 4