1. 概要

このチュートリアルでは、可能な限り最悪の方法でリストを並べ替える方法を学習します。 はい、最悪の方法です。

2. 最悪のアルゴリズム

2.1. 悪いとは限らない

アルゴリズムの科学のあまり知られていないが重要な分野は、並べ替えリストの最もパフォーマンスの低い方法の研究に専念しています。

可能な限り最悪の方法で物事を行う方法の研究には、明らかな知的魅力があります。 しかしまた、物事をひどく行う方法を学ぶことには教育的または教育学的価値があります。 物事がどのように行われるべきでないかを知っているとき、私たちは同時に物事が代わりにどのように行われるべきかを知っています。

さらに、アルゴリズムで最もパフォーマンスの低いものが特に必要な場合があります。 これは、計算が何らかの現実世界の意味を持つ場合であり、その最大の利点または有用性は、最長の計算時間から生じることを示唆しています。

トラバースする迷路があるとしましょう。 通常、グラフ理論では、このタスクを実行する最速または最短経路を調べます。

ただし、迷路が特に美しい現実世界の迷路である場合は、代わりに最長の道を進むことで美的な喜びを引き出すことができます。

同じ引数がソートアルゴリズムに有効です。 特に複雑な方法でリストをソートするという知的課題は、パフォーマンスの悪いアルゴリズムを、それを構築するプログラマーにとって知的に満足させ、満足させる可能性があります。

2.2. 教育学的価値とベンチマーク

パフォーマンスが最も悪いアルゴリズムを研究することには、それらを構築するときに箱の外で考えることを教えることの教育学的価値もあります。 すぐにわかるように、パフォーマンスが最も悪いものの多くは、一見、終わりがないと見なされます。 ただし、十分な創造力があれば、予期しない終了条件が見つかる可能性があります。

現代のコンピュータサイエンスを研究するとき、この考えを理解することには実用的な価値があります。 計算が物理媒体で行われると考えると、アルゴリズムの制約ではなく物理的な制約を利用して、最終的に計算を終了させることができます。これは、終了条件を調べるときに特に重要です。量子アルゴリズムの。

量子プログラムの終了分析では、それらの終了を引き起こす1つの典型的な物理現象は、量子デコヒーレンスです。これは、アルゴリズムプロセスではなく、純粋に物理的なプロセスです。 アルゴリズム分析の焦点を、その手続き的または数学的側面から、コンピューティングシステムの物理的埋め込みに移すことを学ぶ場合、これは、古典的計算から量子計算の研究への移行に役立ちます。

最後に、パフォーマンスが最も悪いアルゴリズムは、開発中の他のアルゴリズムのベンチマークとしても役立ちます。 理論上の最悪のパフォーマンスよりもパフォーマンスが悪いものを開発できた場合、の可能性は、お客様がそれに満足しない可能性があります。

3. ボゴソート

3.1. ボゴソートの定義

世界的に高く評価されている最悪の並べ替えアルゴリズムは、 Bogosort であり、後で説明する理由から、MonkeySortまたはRandomSortと呼ばれることもあります。 ボゴソートは、確率論では、特定の現象が可能である場合、それは最終的に発生するという考えから発展しました。

ボゴソートは、要素の配列から始まります。

次に、要素がソートされているかどうかをチェックします。これには時間がかかると想定されます。 そうでない場合、ボゴソートはそれらの位置をランダム化します。

次に、配列がソートされているかどうかを再度チェックし、そうでない場合はランダム化を繰り返します。 次に、このプロセスは必要な回数だけ繰り返され、配列をチェックしてソートされていることがわかると、最終的に終了します。

3.2. 計算時間

ソートされた配列が厳密に単調である場合、任意のランダム化が必要なものになる確率はです。 これは、予想される計算時間がであるということを意味します。これにより、ボゴソートは次の非常に低い値に対してのみ実行可能になります。

また、有限の時間内に解決策が見つかるという保証もありません。 このため、ボゴソートの計算時間の最悪のシナリオはです。

4. 私たちはもっと悪いことをすることができますか？

しかし、私たちはもっとうまくやることができます。つまり、もっと悪くすることができます。 ここでは、ボゴソートの非効率性を上回り、最終的にはソートされた配列で終了するいくつかの手順を研究します。

4.1. ソフトエラーの悪用

最初の方法は、電子システムのいわゆるソフトエラーを利用します。 半導体メモリチップが電離粒子に遭遇した場合、これはチップの状態の混乱とそれに続く保存されたデータの変化につながる可能性があります。 配列がメモリチップに格納されており、そのすべての部分がそのような粒子に遭遇する可能性が高いと想像すると、それに応じて並べ替えアルゴリズムを開発できます。

  • まず、アレイが正常かどうかを確認します
  • そうでない場合は、しばらく待ってからもう一度テストします

ある時点で、十分なシングルイベントアップセットが発生します。 それらの結果として、メモリチップには最終的にソートされた配列が含まれます。

4.2.  宇宙には本質的な秩序があります

2番目の方法は、配列をソートすることの意味についての考察から導き出されます。 もちろん、配列に何らかの順序の要素が含まれている場合、配列はソートされます。 ただし、問題は次のようになります。どの基準に従って、どの順序を適用するかを決定しますか？

インテリジェントデザインの理論は、宇宙は固有の秩序を持っていると述べています。 要素のリストについて、その特定の順序を観察する確率は非常に小さいことがわかっています。 実際、それはまさにです。

これは非常に小さいので、適切なベイズ推論を使用すると、未知の暗黙の順序によってその特定のパターンが観察されると推測できます。 もちろん、この順序は人間には理解できませんが、それでも存在します。 結果として、このインテリジェント設計アルゴリズムを開発できます。

  • まず、要素の配列を検討します
  • 次に、宇宙には固有の順序があるため、配列にも1つあることがわかります。

これは、時間内に実行できる唯一の並べ替えアルゴリズムであり、実際には、操作をまったく実行せずに要素を適切に並べ替えます。

4.3. エベレッティアンソーティング

最後に、量子力学のEverettian解釈に基づくアルゴリズムを開発することもできます。 古典的なコンピュータのメモリは、デコヘードはまだ量子システムであるため、量子バージョンのBogosortを開発できます。

  • まず、配列をランダム化します
  • 次に、配列が正しい順序になっていない場合、宇宙を破壊します

ソートされた配列が存在する幸運な世界にいる場合、アルゴリズムは1回だけ実行されます。 運が悪ければ、その実行には世界中で常に時間がかかります。 実際、時間自体も終了すると、アルゴリズムは終了します。

5. 結論

この記事では、ボゴソートよりもさらに悪いソートアルゴリズムを研究しました。