QuickSelectの複雑さの分析
1. 序章
このチュートリアルでは、 QuickSelect のワーストケース、ベストケース、および平均ケースの時間計算量を分析します。 これは、-element配列()で-番目に大きい要素を見つけるためのアルゴリズムです。 その発明者に敬意を表して、それをHoareの選択アルゴリズムとも呼びます。
2. クイックセレクト
QuickSelectはQuickSortに似ています。 主な違いは、並べ替えアルゴリズムは分割後に両方のサブアレイで繰り返されるのに対し、選択アルゴリズムは、おそらく-番目に大きい要素を含むサブアレイでのみ繰り返されることです。
QuickSelectが検索中に行うステップをうまく視覚化できます。
2.1. パーティショニング
アルゴリズム1は、入力配列を分割してピボット要素を選択する方法を指定しないため、QuickSelectの一般的な形式です。 何年にもわたっていくつかの方法が登場してきました。 分析が最も簡単なため、このチュートリアルではランダムピボット選択を使用したLomutoパーティショニングを使用します。 他のアプローチは、同じまたは同様の複雑さを持っているか、同様に分析することができます。
簡単に言うと、Lomutoは入力配列内のランダムな要素をピボットとして選択し、それを最後の要素と交換し、配列を1つのループに分割してから:まで繰り返します。
3. QuickSelectの最悪の場合の複雑さの分析
最悪のシナリオの複雑さの限界を導き出す前に、まずその構造を決定しましょう。
3.1. 最悪のシナリオの構造
QuickSelectは、再帰呼び出しごとに元の配列の一部を破棄することがわかります。
- と
- と
ただし、最悪の場合が発生するには十分ではありません。 求められている要素に常に右からアプローチするとします。 その結果、それを見つける前に再帰呼び出しを行います。 一方、左からしか近づかないと電話をかけます。 これは、またはの場合にのみ最悪のシナリオです。 の場合、-番目の呼び出しで-番目に大きい要素を見つけるために、アルゴリズムは、他のすべての要素をピボットとして選択してからに到達する必要があります。 したがって、QuickSelectは、最悪の場合、両側から要素にアプローチします。
3.2. 解析
-element配列のLomutoパーティショニングは、比較と多くてもスワップを実行します。 したがって、その複雑さはです。 -element配列を検索するときにQuickSelectが実行するステップ(比較とスワップ)の数として示しましょう。 QuickSelectは常にサブアレイのサイズを縮小して再帰するため(無視されたサブアレイは空であり、ピボットは他のサブアレイに含まれていないため)、次の繰り返しが成り立ちます。
(1)
それを展開すると、次のようになります。
したがって、QuickSelectは、最悪の場合、2次の複雑さです。
4. QuickSelectのベストケースの複雑さの分析
最良のケースは、QuickSelectが最初の呼び出しでピボットとして-番目に大きい要素を選択した場合に発生します。 次に、アルゴリズムは最初の(そして唯一の)パーティショニング中にステップを実行し、その後終了します。 したがって、QuickSelectが最適です。
5. QuickSelectの平均ケース複雑性分析
アルゴリズムの平均的なケースの複雑さを判断する前に、平均的なケースを分析することの意味を考えてみましょう。 より正確には、平均して、確率論からの用語である期待を意味します。
5.1. 予想される(平均)時間計算量
アルゴリズムの予想される複雑さは、すべての可能な入力の空間にわたるその複雑さの予想です。つまり、入力はランダムで次の確率分布と見なされます。 次に、その分布の下で期待値を見つけます。 通常、分布は均一であると想定しています。 つまり、すべての入力が同じように考えられるということです。
アルゴリズムが現実の世界で遭遇する入力の実際の分布はわかりませんが、
入力配列が一様分布に従うという仮定の下で、平均的なケースは、すべての可能な入力にわたって平均化された複雑さを表します。 ただし、入力配列をランダムにシャッフルするか、ピボット要素をランダムに選択する場合、分析する平均的なケースは、入力配列でのQuickSelectのすべての可能な実行にわたって平均された複雑さを表します。
5.2. QuickSelectのランダムモデル
QuickSelectの場合、すべての要素が互いに異なる場合のみを考慮します。重複が含まれていないと想定しているため、の順列と見なすことができます。つまり、次のことができます。抽象要素の代わりにからの数字を使用します。 各要素は範囲内で一意のランクを持っているため、に切り替えることは正当化されます。また、同じ複雑さを持っているため、重複のあるケースは無視できます。
各呼び出しでピボットをランダムに選択するため、ピボットのランク()は。上の一様分布に従います。
QuickSelectの予想される複雑さを、入力サイズで表現します。 比較の数のみを追跡します。 各パーティショニングのスワップの数は、比較の数によって上から制限されます.
5.3. 解析
確率変数を定義しましょう:
(2)
数値の配列を検索するときにQuickSelectが行う比較の総数は、次のようになります。
(3)
予想される、つまり、サイズの入力の平均比較数は次のとおりです。
(4)
ここで、の確率はです。 どうすれば計算できますか?
考慮すべき3つのケースがあります。
- ケース1:
- ケース2:
- ケース3:
QuickSelectは比較せず、ピボットまたはそれらの間にある数値として選択されます。 上記の3つのケースのそれぞれに当てはまります。 ピボットになると、アルゴリズムは探している番号を見つけたので、検索は停止します。 ピボットがとの間にある場合、パーティショニング中に左と右のサブアレイになります。 したがって、アルゴリズムは、呼び出しで同じサブ配列に含まれる要素のみを比較できます。
ただし、QuickSelectは、再帰呼び出しでピボット要素を他のすべての番号と比較します。 したがって、比較するために、Quickselectは、対応するケースの範囲から他の数値の前に、またはピボットとして選択する必要があります。
ピボットはランダムに分散されているため、範囲からの任意の整数の選択確率はです。 の選択とからの最初のピボットは相互に排他的なイベントであるため、それぞれの場合に取得する確率を合計できます。
(5)
ケースごとに合計に分割し、取得した合計を合計することができます。 ケース1では、次のようになります。
(6)
ケース2でも同様の結果が得られます。
(7)
ケース3も次のようになります。
(8)
定義を使用しました。 すべてのために、私たちは持っています:
(9)
したがって、QuickSelectは平均的なケースです。
6. 他のパーティショニングスキームとピボット選択戦略の議論
Lomutoパーティショニングを使用するQuickSelectを分析しましたが、Hoareパーティショニングなどの他の代替手段があります。 入力配列を両端からスキャンします。 Lomutoパーティショニングよりもわずかに多くの比較を実行しますが、平均してスワップの数は少なくなります。 それでも、HoareまたはLomutoパーティショニングを使用するかどうかに関係なく、QuickSelectの複雑さは同じです。
両方のパーティショニングスキームで決定論的にピボットを選択し、常に最初、最後、またはその他の要素を選択する場合があります。 ただし、ここで行ったようにランダムに選択することもできます。 どちらの戦略も漸近的な複雑さは同じですが、ランダムに選択すると、実際には実行時間が速くなる可能性があります。
ただし、最悪の場合の複雑さをに減らす方法があります。これは、中央値の中央値でピボットを選択することです。 これは、入力配列の上位30% aよりも小さい要素と下位30% e要素よりも大きいことが保証されている要素を返すアルゴリズムです。 これは、最悪の場合、入力配列のサイズを0.7分の1に減らすことを意味します。これにより、次の繰り返しが発生します。
(10)
そして、線形の最悪の場合の複雑さをもたらします:
(11)
7. 結論
この記事では、QuickSelectの最悪、最良、および平均的なケースの時間計算量を分析しました。 HoareまたはLomutoパーティショニングを使用するアルゴリズムの通常の実装は、最悪の場合は2次の複雑さですが、ピボット選択戦略に関係なく、平均および最良の場合は線形です。ただし、中央値の中央値を使用するピボットを選択する中央値は、最悪の場合でもlinearランタイムになります。