23

最近のSaturday Morning Breakfast Cereal comicで、著者は自然数のリストをソートするための Frog Sort と呼ばれるアルゴリズムについて説明しています。アルゴリズムはコミックで説明されていますが、簡単にするためにここに転載しました。

  1. ソートする自然数ごとに、その数のハエが入った箱を作ります。
  2. 各ボックスにカエルを入れます。
  3. すべてのカエルがまだ箱から飛び出しているわけではありませんが、
    1. カエルが箱から飛び出すのを待ちます。
    2. 最初に箱に入れたハエの数を書き留めます。
  4. 結果の数字のシーケンスは元の数字のリストですが、ソートされた順序になっています。

このアルゴリズムは、すべてのカエルが同じ割合でハエを食べると仮定します。その結果、箱から最初にジャンプしたカエルは、それぞれに飛ぶハエの数が最も少ないカエルになり、2 番目のカエルは食べるハエの数が 2 番目に少ない、というようになります。

コミックの途中で、教師が生徒に「最大ステップ数は?」と尋ねます。これは、「このアルゴリズムが終了するのに必要な最大ステップ数は?」という意味だと解釈します。つまり、アルゴリズムの実行時間は? 次に、生徒は「丸太のカエル(箱)」と答えます。

これは、このアルゴリズムの実行時間の正確な分析ですか? それとも作者が悪いの?

4

3 に答える 3

12

このランタイム分析は明らかに間違っています。の自明な Ω ランタイムを取得できますmax(n_elements, largest_element)(n_elementsボックスを作成し、各ボックスが空になるまでにその内容のサイズと同じだけ時間がかかるため)。n時間未満のソートアルゴリズムは...非常に驚くべきものです。

インターネットのどこかでさらに分析を見つけたい場合、このアルゴリズムはスリープソートと同等です。そのばかげたアルゴリズムに慣れていない場合は、ここに 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 でハエを食べることができると仮定します。つまり、カエルがハエを 1 匹食べるのに r 秒、カエルが 10 個のハエを食べるのに 10 r 秒かかります。また、カエルが空の箱から飛び出すのに j 時間かかると仮定します。

また、セットアップ時間も考慮に入れる必要があります。ハエ、カエル、箱が無制限に手元にあると仮定して、箱を手に入れるのに b 時間、ハエを 1 個箱に入れるのに y 時間かかるとしましょう。最後に、カエルを箱に入れるのに f 時間かかるとします。簡単にするために、明示的に指示するまでカエルはハエを食べ始めないと仮定します。

最後の詳細 - 数値を書き留めるのに w 時間かかると仮定しましょう。

その場合、このアルゴリズムの実行時間は次のようになります。ソートする数値のリストが x 1、 x 2、...、 x nであるとします。その場合、すべてのボックスをセットアップするために必要な時間は、n(b + f) + y(Σx i ) になります。この理由は、n 個のボックスを取得し、各ボックスに 1 匹のカエルを配置する必要があり (したがって第 1 項)、さらに各ハエに対して y 単位の時間 (したがって第 2 項) を入れる必要があるためです。

アルゴリズムの過程で、カエルが箱から飛び出したときに、各数値を正確に 1 回書き留める必要があります。これは、アルゴリズム全体で、ソートされたシーケンスを書き留める nw 作業を行うことを意味します。

最後に、すべてのカエルが終了するまでにかかる時間を考慮する必要があります。すべてのカエルが並行して食べているので、気にする必要があるのは、食べるハエが最も多いカエルだけです。このカエルは x max個のハエを食べます。x maxは入力リストの最大数です。したがって、カエルが食べるのに費やす時間は rx maxで与えられます。最後のカエルのジャンプを考慮に入れると、カエルはすべて並行して動作し、まとめて rx max + j 時間で終了します。

これは、アルゴリズムの全体の時間が次のように与えられることを意味します。

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

ここで、個々の操作 (カエルにハエを食べさせる、箱から飛び出させる、カエルを箱に入れるなど) を実行するのに「1 つの作業単位」で十分であると仮定すると、合計所要時間はせいぜい

n + Σ(x i ) + x max + 1

x max ≤ Σx iであることに注意すると、このアルゴリズムの全体的な実行時間はΘ(n + Σx i ) であることがわかります。つまり、実行時間は、並べ替える数値の数と、並べ替える数値の合計サイズの両方に比例します。

このランタイムには対数が含まれていないことに注意してください。そのため、作成者のランタイム分析が正しくないとすぐに結論付けることができます。

最後に、これは非常に悪いソート アルゴリズムであることに注意してください。カウンティング ソートアルゴリズムは、時間 O(n + U) で n 個の自然数をソートできます。ここで、U はソートされる最大値であり、FrogSort よりも漸近的に優れています。基数ソートアルゴリズムは、O(n lg U) 時間でこれを実行できます。これは、U の値が大きい場合に適しています。また、どちらのアルゴリズムも洗練された機械を必要とし、コミックで説明されている設定にはおそらく存在しないでしょう。

お役に立てれば!

于 2012-12-23T23:50:30.547 に答える