クイックソルトのこの特定のバージョンを分析するには？

Question

私はこの擬似コードを持っていると私はこのアルゴリズムの分析時間の複雑さにしたいしかし、私はだから私は、配列の要素が4未満であれば、我々はクイックソートを通してそれを渡すことを知っている

それについて

Proc Sort(A,l,r) 
if(r-l+1<4) 
    then Quicksort(A,l,r) 
    else 
    Sort(A,l,r-3) 
    Sort(A,l+3,r) 

見当がつかないそうでない場合は、配列のサイズを3つ減らしてから左右の部分を渡します。これで、サイズの配列が正確に得られます。< 4問題は再発に至ることができず、わかりませんこのアルゴリズムが最悪の場合の解析でうまくいく場合は、

Answer 1

はまあ、このソート機能 が実際に働くかどうか、実行時間を把握する方法はここに非常に簡単です

：

あなたは配列のサイズの関数としての実行時間のための数学的表現を書き留め：

T（N）= ???

もし、N < = 4なら、Quicksortを呼び出します。今では関数定義は利用できませんが、最大サイズ4の入力で呼び出されるだけなので、その実行時間を定数として扱い、Cと呼ぶことができます。

N> = 4の場合は、Sortをもう一度呼びます。配列は3つ小さくなります。

だから：

T（N）N> = 4のためのT（N-3）×2です。

これで、ランタイム解析に必要なすべての情報が得られるはずです。あなたがここでそれを試して、あなたが立ち往生したときに私たちに戻ってみませんか？