アルゴリズムの実行時間を把握しようとしています。これは、問題を 2/3 のセットに分割することによって機能するソートです (CLR ソートです)。私はそれを思い付くのに苦労しています、これは私が持っているものです：
T(n)=3T([2n]/3)+1 (1 は、再帰呼び出しとは別に、行われる場合と行われない場合がある交換が 1 つあるためです。それが行われたと仮定すると、それは依然として一定のコストに過ぎません。 .)
T(n)=3T([2([2n]/3+1)]/3+1)+1
T(n)=3T([2([2([2n]/3+1)]/3+1)]/3+1)+1
T(n)=3T([2([2([2([2n]/3+1)]/3+1)]/3+1)]/3+1)+1
など......ある時点で最終的に T(n) の基本ケースに到達し、そのランタイムの定数値 1 を取得すると仮定できるまで。これにより、次のことがわかります。
3([2([2([2([2(...........)]/3+1)]/3+1)]/3+1)]/3+1)+1 with logn terms (that's the "......." in the middle). This gives:
3*(2n/3+1)^(logn)+1*logn
3*(2n/3+1)^(logn)+logn
次に、ログのベースが 2n/3+1 である場合、単純に 3*logn+logn に単純化できるので、そうすることができると思います。(漸近記法を行う場合、選択したログの基数は問題にならないということをよく耳にします....)
これが4lognになります。係数は低下して単純に logn になります。
これは正しいです？これを適切に展開したかどうか、またはログ操作が合法であったかどうかはわかりません...また、この最終結果は何ですか--big-O、シータなど。何を見ているのかわかりません。 ..
ありがとう。