1
我想弄清算法的運行時間。這是一種通過將問題分成2/3組（這是CLR排序）的方式。我有一些麻煩提出來，這是我有：試圖找到重複的漸近運行時的問題
T（n）= 3T（[2n]/3）+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。該係數下降，變成簡單的登錄。
這是正確的嗎？我不知道我是否正確地擴展了它，或者如果我的日誌操作是合法的......另外，這個最終結果是什麼 - 大O，θ等等。我不確定我在看什麼。 ..
謝謝。