漫画の作者が間違っていると確信しています。以下は、アルゴリズムのより正式な分析です。
まず、カエルがハエを食べる方法の基本ルールを設定する必要があります。すべてのカエルが一定の割合 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 の値が大きい場合に適しています。また、どちらのアルゴリズムも洗練された機械を必要とし、コミックで説明されている設定にはおそらく存在しないでしょう。
お役に立てれば!