修正後のクイックソートの実行時間= O（Nk）

Question

これは宿題に関する質問であり、私は複雑さを見つけるのではないが、私は最善を尽くしている！

• スリーウェイ分割は、要素をピボットよりも小さい、等しく、大きいグループに分割するクイックソートの変更です。小さい要素と大きな要素のグループだけが再帰的にソートされる必要があります。 N個のアイテムがあり、ユニークな値がk（つまり重複が多い）がある場合、quicksortに対するこの変更の実行時間はO（Nk）であることを示します。私はアイテムを重複しているサブルーチン（NK）を等しくすることを前提とし
  ：

私の挑戦：平均的なケースで

：

木のサブルーチンはこれらの指標になります

• 最初から：0から（i-1）
• 2番目：i - （i + NK-1））
• 第三の：（iはNK + 1） - （N-1）比較の
• 数=（NK）-1

したがって、

T(n) = (n-k)-1 + Sigma from 0 until (n-k-1) [ T(i) + T (i-k)] 

それからそれはしかし非常に悪いスタートであるかもしれないS

を：「私はつもりは続けてるかわからないM $ 希望ヘルプを見つけるために

Answer 1

まずO(nk)の上限は、より強い声明で、最悪の場合、のために証明することができるので、あなたは平均的なケースで見てはいけません。

再帰の可能な最大深さを確認する必要があります。通常のクイックソートでは、最大深度はnです。各レベルについて、実行される操作の総数はO(n)であり、最悪の場合には合計でO(n^2)になります。

ここでは、最大可能深度がkであることを証明することは難しくありません（各レベルで1つの固有値が削除されるため）。O(nk)になります。

Answer 2

I複雑さの中で正式な教育を受けていない。しかし、それを数学的な問題として考えるなら、数学的な証明として証明できます。すべてのソートアルゴリズムのために

あなたは少なくとも一度それぞれを考慮しなければならないn個の要素をソートするため、最良のシナリオは常にO（n）の n個ための要素となります。今、クイックソートの特定の最適化のために、あなたが行ったことは、今、ユニークな値だけをソートするので、問題を単純化します。ピボットと同じすべての値はすでにソートされているとみなされ、すべてのユニークな値が操作のある時点でピボットとして機能することを保証します。これにより、重複が排除されます。

これはNサイズのリストについては、クイックソートは、いくつかの操作をN回（一回、リスト内のすべての位置のための）を実行しなければならないことを意味し、リストをソートしようとしているので、その操作は、検索しようとしていますその値がリストに含まれていますが、ユニークな値を効果的に扱っているため、kがあるため、クイックソルトアルゴリズムは各要素に対してkの比較を実行する必要があります。したがって、N Nサイズリストの操作は、kというユニークな要素で実行されます。要約する

：

• をこのアルゴリズムは、重複した値に対してチェックを排除します。
• しかし、すべてのソートアルゴリズムでは、リスト内のすべての値を少なくとも1回は調べなければなりません。 オペレーション
• リスト内のすべての値について、操作はリスト内の他の値に対する相対位置を見つけることです。
• 重複が削除されるため、チェックする値はkのみです。
• O（NK）