時間一個遞歸算法

-3

這裏的複雜性，我們有一個算法時間一個遞歸算法

T(n) = n-1 + T(i-1) + T(n-i) 
T(1) = 1

如何計算它的時間複雜度？ 我介於1和n之間

i的值是多少？ – Gor

@Gor它沒有值， –

然後這個問題沒有解決方案。 –

我認爲我們應該解決像這樣

如果我= 2，那麼我們有

T(n) = n + T(n-2) = Theta(n^2)

若i = N/2，那麼我們有

T(n) = n-1 + T(n/2 -1) + T(n/2) = Theta(n.logn)

那麼我們就上O（n^2）和算法的順序爲O（n^2）

2016-01-11 10:13:26

我可以認識到這是快速排序算法（隨機快速排序）。我確定這個問題不知何故錯過了總結部分。

好吧！你可以用O(n^2)在這裏使用替代方法。你會發現O(n^2)是最糟糕的時間複雜度。

平均情況有點棘手。然後樞軸可以是從1到n的任何元素。然後分析它。在這裏你也可以申請替代T(n)=O(nlogn)。

2016-01-11 08:20:33 coderredoc

你不應該回答這樣的陳述問題;讓他們以前修好。 –

@YvesDaoust：你以爲我是「渴望餓了」，這就是爲什麼回答它。對於回答這樣的問題，你是正確的。好吧，我會牢記在心。在這種情況下，我對這個問題充滿信心。我應該修好它。無論如何感謝您的注意。我也在學習。保持良好的工作。 – coderredoc

回答