1. 序章


このチュートリアルでは、配列内の最小数を見つけるいくつかの方法を示します。 また、これらのメソッドの複雑さと相互の相対的なパフォーマンスについても説明します。








これらの手法はすべて、配列内の最大数を見つけるという逆の問題に適合させることができます。


2. 問題の説明


数値の配列が与えられた場合、私たちの目標は、最小の要素を見つけて、それらを降順ではない順序で返すことです。


たとえば、との場合、これらはの3つの最小数であるため、解は配列になります。


の場合、問題は配列の最小値を見つけるになります。


3. ナイーブソリューション


配列時間をループして、各パスで最小の数を見つけて削除できます。 このソリューションの時間計算量はです。 配列全体を繰り返しトラバースするため、非効率的です。


もう1つの単純な解決策は、全体を非減少的に並べ替えてから、並べ替えられた配列の最初の要素を取得することです。 このアプローチの問題は、最小のものだけが必要な場合でも、すべての要素をソートすることです。 このメソッドの複雑さはソートアルゴリズムによって異なりますが、が。よりもはるかに小さい場合は非効率になります。 たとえば、最小の5つだけが必要な場合、数値の配列全体を並べ替えることは意味がありません。


4. 最小ヒープに基づくソリューション


min-heapを使用するとさらにうまくいくことができます。 二分木と考えると、最小ヒープには、各ノードがその子以下であるという特性があります。 したがって、ルートノードは最小ヒープの最小値です。


配列から最小ヒープを構築したら、そのルートをポップして、その中の最小の要素を取得できます。 次に、残りのヒープを処理してヒーププロパティを保持し、新しいルートをポップして2番目に小さい数を取得します。


プロセス時間を繰り返すと、目的の出力が得られます。


 


フロイドのアルゴリズムを使用して、時間内にヒープを構築できます。 ルートをポップして残りをヒープ化するには時間がかかるため、このような手順は合計で時間内に実行できます。 したがって、全体の複雑さは次のようになります。 


      


がの線形関数である場合（たとえば、下を探す場合）、複雑さは次のようになります。 


      


これは、バイナリ比較のみを使用するソートアルゴリズムの複雑さの下限です。


5. 最大ヒープに基づくソリューション


max-heapを使用して問題を解決できます。 最大ヒープは最小ヒープに似ていますが、唯一の違いは、各最大ヒープのノードがその子以上であるということです。 したがって、max-heapのルートにはその最大値が含まれます。


最初に、ソートされていない配列の最初の要素を取得し、それらを最大ヒープに入れます。 次に、残りの要素を繰り返し処理して、ルートと比較します。


現在の要素（）がルートよりも低い場合、少なくともルート（現在ヒープ内および比較したばかりのヒープ内）以下の要素があることがわかります。ルートを最小数にすることはできません。 したがって、ルートをに置き換え、ヒープを処理してそのプロパティを保持し、配列内の次の要素に移動します。


それ以外の場合、がルートより小さくない場合は、配列内の少なくとも他の数値以上であることがわかっているため、最小の1つにすることはできず、破棄できます。


 


 


フロイドのアルゴリズムを使用して、時間内にヒープを構築できます。 最悪の場合、最初にヒープから出た各要素はルートよりも低くなるため、ルート置換操作時間を実行します。 結果として、最悪の場合の複雑さは


      


がの線形関数である場合、複雑さは次のようになります。 


      


6. QuickSelSort


このアプローチは、QuickSelectとQuickSortを組み合わせたものです。


まず、QuickSelectを使用して、-番目に小さい数値を見つけます。 入力配列の-番目の位置に配置し、通過する位置に小さい数値を配置しますが、並べ替えは行いません。


これらの数値を最小から最大に並べ替えるには、QuickSortをに適用します。 QuickSortは-番目に小さいことがわかっているので、QuickSortで処理する必要はありません。


 


 


アプローチの最悪の場合の複雑さは 


      


その平均的な複雑さは 


      


 これはかなり良いです。 ただし、がの線形関数である場合、平均の複雑さはであることがわかります。


QuickSelSortの注目すべき利点は、多くのライブラリで利用可能でパフォーマンスが調整された2つのアルゴリズムを使用するため、最初から実装する必要がないことです。


7. 部分的なクイックソート


部分的なクイックソートは、通常のクイックソートを修正したものです。 違いは、前者は、おそらく最小の要素を含む配列の部分に対してのみ再帰呼び出しを行うことです。


通常のクイックソートでは、サブアレイを取得し、ピボットを選択して、2つの小さなサブアレイとに分割します。 QuickSortの目的は配列全体をソートすることであるため、2つの再帰呼び出しを行う必要があります。1つは左側のサブ配列用で、もう1つは右側のサブ配列用です。


対照的に、PartialQuickSortは常に正しいサブアレイをソートするとは限りません。


の場合、最小数が含まれていないため、PartialQuickSortは正しいサブ配列を完全に無視します。 後の番号はすべて左側のサブ配列にあるため、でのみ再帰呼び出しを行います。


の場合、検索された番号の一部がに含まれているため、再帰的に呼び出す必要があります。


 


 




ピボットをランダムに選択すると、QuickSelSortの場合と同様に、Partial QuickSortの最悪の場合の複雑さはであり、予想される複雑さはです。 ただし、部分的なクイックソートでは、平均して比較が少なくなります。


8. 中央値の中央値を持つ部分的なクイックソート


パーシャルクイックソートの最悪の場合の時間計算量をに減らす方法があります。 これは、中央値の中央値と呼ばれるアルゴリズムを使用してピボット要素を選択することで実現できます。


8.1. 中央値の中央値


QuickSortおよびPartialQuickSelectアルゴリズムは、再帰呼び出しの前に配列サイズを一定の係数で減らすと、処理する配列のサイズが再帰の深さとともに指数関数的に減少するため、最高の漸近パフォーマンスを示します。


中央値の中央値（MoM）は、正確にそうするピボット選択アルゴリズムです。


MoMは、入力配列の下部と上部の間にある要素を返します。 したがって、返されたピボットは、入力配列をとの間の比率で分割します。 最悪の場合、入力のサイズを係数で縮小します。 これは既知の定数による削減であるため、入力サイズは指数関数的に減少します。


8.2. 複雑さの分析


MoMは時間内に実行されます。 部分クイックソートは各呼び出しで比較を行うため、MoMによって引き起こされるオーバーヘッドによって、呼び出しの漸近的な複雑さが変わることはありません。 ただし、最悪の場合の時間計算量は次のように減少します。 


      


 これは、PartialQuickSortの汎用バージョンの平均的な複雑さです。


9. ハイブリッド部分クイックソート


MoMを使用したPartialQuickSortは、最悪の場合の時間計算量がありますが、実際には、ほとんどのアレイで漸近的に劣るバージョンのPartialQuickSortよりも実行速度が遅くなります。 MoMは最悪の場合の複雑さを改善しますが、追加のオーバーヘッドのためにほとんどの入力でアルゴリズムの実行が遅くなります。


実用的な効率を維持し、同時に最悪の場合の複雑さを軽減する方法があります。 IntroSelectからインスピレーションを得ています。


アイデアは、ピボットをランダムに選択する通常の部分クイックソートから始めることです。 手元の入力がアルゴリズムの最悪の場合の動作を引き起こさず、ランダム選択を使用しても安全であると想定しています。 かなりの時間、私たちは正しいでしょう。 平均ケースモデルは、ほとんどの入力配列に適用されます。 ただし、ランダムな選択によって非効率的なパーティショニングが発生することに気付いた場合は、最悪のケースを回避するためにMoMにフォールバックし、代わりにそれを使用します。


2つの簡単なルールでMoMに切り替えることができます。


    

  • すべての再帰呼び出しで入力配列サイズを追跡します。 連続する呼び出しで入力の長さが半分にならない場合（は事前に設定された定数）、MoMに切り替えます。
    • 

  • 再帰呼び出しで入力配列サイズの合計を追跡します。 呼び出しの合計が、を超えていることに気付いた場合、ここで、MoMに切り替えます。
    • 



これらのルールは、再帰の深さを制限して、最悪の場合の複雑さがであることを保証します。 さらに、ほとんどの入力でアルゴリズムの効率を維持します。 2番目の戦略がどのように機能するかを見てみましょう。




10. 複雑さの比較




QuickSortとQuickSelectに基づくすべてのメソッドは、同じ平均ケース時間計算量を持っていることがわかります。 ただし、QuickSelSortとPartial QuickSortには、最悪の場合の時間計算量があります。 漸近的には同等ですが、実際には後者の方が効率的です。


部分クイックソートでピボットを選択するためにMoMを使用する場合、最悪の場合の複雑さをに減らしますが、MoMによって引き起こされるオーバーヘッドのために、非効率的なアルゴリズムになります。 ハイブリッドパーシャルクイックソートは、MoMを使用したパーシャルクイックソートと同じ漸近的な複雑さを持っています。 ただし、ランダムな選択によって非効率的なパーティショニングが発生する場合にのみMoMを使用するため、実際には高速です。


ヒープは興味深い選択肢を提供します。 ただし、実際のパフォーマンスは、よりどれだけ大きいかによって異なります。


がの線形関数である場合、平均的な場合、すべてのアプローチは対数線形になります。 MoMを使用した部分クイックソート、ハイブリッド部分クイックソート、およびヒープベースのソリューションも最悪の場合になります。


11. その他のアプローチ


QuickSortの代わりに、MergeSortなどの他の並べ替えアルゴリズムを適応させることができます。


フロイド-リベスト選択アルゴリズムに基づいてソリューションを作成することもできます。 QuickSelectと同じように、配列内で-番目に小さい要素を検出しますが、平均して高速です。


12. 結論


このチュートリアルでは、配列内の最小数を見つけるいくつかの方法を示しました。 私たちはほとんどのソリューションをQuickSortに基づいていますが、ヒープに着想を得た2つのアプローチを提示し、問題を解決するために適応できる他のアルゴリズムについても言及しました。