如何解決遞歸複雜度T（n）= T（n/4）+ T（3n/4）+ cn

Question

我正在使用遞歸樹解決這個問題。每個級別的總成本爲n，樹的深度介於log (n) base 4和log (n) base 4/3之間。直覺上來說，我認爲解決方案最多是級別數乘以每個級別的成本。 O(cn log (n) base 4/3) = O(n log n)。我想知道如果我的方法解決這個問題，我的解決方案是正確的？

Answer 1

想想這樣：對於第一個日誌遞歸樹的n層，這些層之間的工作總和將爲cn，因爲如果總結所有子問題的總大小，應該總共n，所以總的工作是cn。這意味着完成的工作是Ω（n log n）。

假設在樹的每一層完成的工作總和爲O（n）（當它在樹中越來越低時它實際上會下降，所以你可以上限工作，所以這是一個上限）和高度是log _4/3 n。這給出了O（n log n）的工作上限。

由於完成的工作是Ω（n log n）和O（n log n），所做的工作更合適Θ（n log n）。

希望這有助於！

Answer 2

編輯：失蹤的OP，並回答了錯誤的解決方法，下面是我的精緻嘗試

直觀地說，你是對的。

對於更正式的方法，您可以用數學來證明它。

的魔術是在這裏：Akra-Bazzi theorem這是主定理

的更一般的版本對於關係T(n) = T(n/4) + T(3n/4) + cn

我們得到了g(n) = cn, k = 2, a1 = a2 = 1, b1 = 1/4, b2 = 3/4

通過定理，我們要解決p表示a1b1^p + a2b2^p = 1這顯然是p = 1

然後T(n) = O(n^p * (1+integration(1/n dn))) = O(n*(1+log(n))) = O(nlogn)

符合我們的猜測