復發T（N）的= T（N/3）+ T（2N/3）

Question

我在網上搜索到了這一點，但我似乎只找到一個類似的公式答案：

T(n) = T(n/3) + T(2n/3) + cn 

但一個我試圖解決的是：

T(n) = T(n/3) + T(2n/3) 

基本情況：我們可以假設T(a) = Theta(1)任何常量a。

我成功地證明了（通過歸納）T(n) = O(n*log(n))。我認爲答案應該是Theta(n*log(n))，但我不能證明T(n) = Omega(n*log(n))。

所以我的問題是 - 我正確的答案是O(n*log(n))，而不是Theta(n*log(n))？如果這是真的，真的會很大......

如果我錯了，我當然會說明在何處我卡在感應過程...

謝謝！

P.S.如果您需要，請嘗試使用歸納解釋，因爲我還沒有學習解決這些問題的所有方法。

Answer 1

由於T（n）= n滿足基本情況和遞歸，所以你不能證明它是Omega（n log n）。