23

在最近的周六早餐谷物漫画中，作者描述了一种称为 Frog Sort 的算法，用于对自然数列表进行排序。该算法在漫画中有所描述，但为简单起见，我在这里重印了它：

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

该算法假设所有青蛙以相同的速度吃苍蝇。结果，第一个从盒子里跳出来的青蛙将是每只青蛙数量最少的青蛙，第二只青蛙吃的苍蝇数量第二少，以此类推。

在漫画的中间，一位老师问学生“最大步数是多少？”我将其解释为“该算法终止所需的最大步数是多少？” 也就是说，算法的运行时间是多少？然后学生回答“原木青蛙（盒子）”。

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

4

3 回答 3

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
于 2012-12-24T02:13:36.533 回答
5

我很确定漫画的作者是错的。下面是对该算法的更正式的分析。

首先，我们需要为青蛙如何吃苍蝇制定一些基本规则。我假设所有的青蛙都能以恒定的速率 r 吃掉苍蝇。也就是说，一只青蛙吃掉一只苍蝇需要 r 秒，一只青蛙吃十只苍蝇需要 10r 秒，等等。接下来，让我们做一个（合理的）假设，所有的青蛙都在并行吃东西。我们还假设一只青蛙从一个空盒子里跳出来需要 j 时间。

我们还需要考虑设置时间。假设我们手头有无限数量的苍蝇、青蛙和盒子，假设得到一个盒子需要 b 时间，将一只苍蝇放入盒子需要 y 时间。最后，我们假设将一只青蛙放入一个盒子需要 f 时间。为简单起见，我们假设青蛙在我们明确指示它们之前不会开始吃苍蝇，因此在其他青蛙之前放入盒子中的青蛙不会抢占先机。

最后一个细节——假设写下一个数字需要 w 时间。

在这种情况下，该算法的运行时间如下所示。假设我们要排序的数字列表是 x 1 , x 2 , ..., x n。在这种情况下，设置所有框所需的时间为 n(b + f) + y(Σx i )。这样做的原因是我们需要得到 n 个盒子并将一只青蛙放入每个盒子（因此是第一项），再加上每只苍蝇的 y 单位时间（因此是第二项）。

在算法的过程中，当青蛙跳出它的盒子时，我们需要准确地写下每个数字一次。这意味着在整个算法中，我们将做 nw 工作来写下排序的序列。

最后，我们必须考虑所有青蛙需要多长时间才能完成。由于所有的青蛙都在同时吃东西，所以我们只需要关心吃苍蝇最多的青蛙。这只青蛙将有 x max苍蝇要吃，其中 x max是输入列表中的最大数量。因此，青蛙吃东西所花费的时间由 rx max给出。考虑到最后一只青蛙的跳跃，所有并行工作的青蛙将在 rx max + j 时间内共同完成。

这意味着算法的总时间由下式给出

n(f + b) + yΣx i + nw + rx max + j。

如果我们现在假设“一个工作单元”足以完成任何单个操作（让青蛙吃掉一只苍蝇，或者从盒子里跳出来，或者把一只青蛙放进盒子里等等），那么总的所需时间最多

n + Σ(x i ) + x最大值+ 1

注意到 x max ≤ Σx i，我们得到该算法的整体运行时间为Θ(n + Σx i )。换句话说，运行时间与要排序的数字数量和要排序的数字的总大小成正比。

注意这个runtime里面没有任何对数，所以我们马上可以断定作者的runtime分析是不正确的。

最后，请注意这是一个非常糟糕的排序算法。计数排序算法可以在O(n + U) 时间内对 n 个自然数进行排序，其中 U 是要排序的最大值，在渐近上优于 FrogSort。基数排序算法可以在 O(n lg U) 时间内完成此操作，这对于较大的 U 值更好。再一次，这两种算法都需要复杂的机器，这在漫画描述的设置中可能不存在。

希望这可以帮助！

于 2012-12-23T23:50:30.547 回答
0

这不是一个答案，但扎克本人对此很感兴趣。它是 cbrain 深奥编程语言http://esolangs.org/wiki/Cbrain中复活节彩蛋的一部分。使用 OpenCOBOL 编译的 bf 衍生产品。为了摆脱困境，条件价值公平可以设置为 2 而不是 1。 COBOL 中的 frogSort。

      *> ********************************************************
      *>  frogSort, called for help with 10-94, request for count
      *> ********************************************************
       identification division.
       program-id. frogsort.
       data division.
       working-storage section.
       01 opinion          usage binary-long.
       01 shared-value     pic 99.
          88 fair          value 1.
       01 caveman-count    pic x(12) value "[-]+++++++++".
       01 spacer           pic x(10) value spaces.

       linkage section.
       01 jars.
          05 flies        pic 9 occurs 21 times.

      *> ********************************************************
       procedure division using jars.
       start-here.
       move function length(jars) to shared-value
       display "Grog sort jars.  frogSort" end-display
       display "http://www.smbc-comics.com/?id=2831" end-display
       .

       forkyourself.
           call "fork" returning opinion end-call
           if opinion is zero then
               subtract 1 from shared-value
               if not fair then go forkyourself.
       .

       call "sleep" using by value flies(shared-value) end-call
       display
           "Jar: " function char(shared-value + 65) " reporting "
           caveman-count(1 : flies(shared-value) + 3) " flies,"
           spacer(1 : 10 - flies(shared-value))
           "that would be " flies(shared-value) " to you, futureman."
       end-display
       call "wait" using by value 0 end-call

       stop run returning 107.
       end program frogsort.

用 CALL "frogsort" USING ""012345678901234567890" END-CALL 踢复活节彩蛋

$ ./cbrainrun 
10-12 Welcome to cbrain v0.42
cb: 1094
cb: help
Grog sort jars.  frogSort
http://www.smbc-comics.com/?id=2831
Jar: U reporting [-] flies,          that would be 0 to you, futureman.
Jar: K reporting [-] flies,          that would be 0 to you, futureman.
Jar: A reporting [-] flies,          that would be 0 to you, futureman.
Jar: L reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: B reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: M reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: C reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: N reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: D reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: O reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: E reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: P reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: F reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: Q reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: G reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: R reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: H reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: S reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: I reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: T reporting [-]+++++++++ flies, that would be 9 to you, futureman.
Jar: J reporting [-]+++++++++ flies, that would be 9 to you, futureman.
于 2013-04-08T14:47:59.730 回答