我對於簡化這種復發關係感到困惑：c（n）= c（n/2）+ n^2。簡化復發關係c（n）= c（n/2）+ n^2
所以我第一次：
C（N/2）= C（N/4）+ N^2個 所以 C（N）= C（N/4）+ N^2 + N^2個 C（N）= C（N/4）+ 2N^2
C（N/4）= C（N/8）+ N^2 所以 C（N）= C（N/8）+ 3N^2
我排序注意到雖然一個模式：
2升高到任何係數的功率是在前面「n^2」給出了n的結果分母。
我不確定這是否有幫助。
我只是不明白我將如何簡化這種復發關係，然後找到它的theta符號。
編輯：其實我只是把它再次出來，我得到了c（n）= c（n/n）+ n^2 * lgn。
我認爲這是正確的，但我不確定。另外，我如何找到那個theta符號？它只是theta（n^2lgn）？
首先，確保替代n/2到處n在LHS將c(n/2)時出現在原來的遞推關係。
即
c(n/2) = c(n/4) + (n/2)^2
你的直覺是正確的，因爲它是問題的一個非常重要的組成部分。在我們達到1之前，您可以用2來劃分n多少次？
讓我們8爲例
8/2 = 4
4/2 = 2
2/2 = 1
你看到它的3，這事實證明是log(8)
爲了證明THETA符號，它可能會有所幫助檢查出master theorem 。這是證明遞歸關係複雜性的非常有用的工具。
使用主定理的情況下3，我們可以看到
a = 1
b = 2
logb(a) = 0
c = 2
n^2 = Omega(n^2)
k = 9/10
(n/2)^2 < k*n^2
c(n) = Theta(n^2)
的直覺，爲什麼答案是Theta(n^2)是，你有n^2 + (n^2)/4 + (n^2)/16 + ... + (n^2)/2^(2n)，這不會給我們lognn^2 S，而是越來越小n^2 s
那麼它會是c（n）= c（n/n）+ n^2 * lgn嗎？ – user3421510
@ user3421510看到我的更新的答案制定出主定理的案例3。 –
讓我們回答一個更一般的問題，以重複表格： r(n) = r(d(n)) + f(n)。這些功能有一些限制，需要進一步討論，例如如果x是d的固定點，那麼f(x)應該是0，否則沒有任何解決方案。在你的具體情況下，這個條件是滿足的。
整理上式，我們得到的是r(n) - r(d(n)) = f(n)，我們得到的直覺r(n)和r(d(n))都是一些術語的總和，但r(n)比r(d(n))一個多學期，這就是爲什麼f(n)的差異。另一方面，r(n)和r(d(n))必須具有相同的「形式」，因此前面提到的總和中的術語數量必須是無限的。
因此，我們正在尋找一個可伸縮的總和，其中，用於r(d(n))條款取消了所有，但一個條款r(n)：
r(n) = f(n) + a_0(n) + a_1(n) + ...
- r(d(n)) = - a_0(n) - a_1(n) - ...
後者意味着
r(d(n)) = a_0(n) + a_1(n) + ...
而剛剛通過替換d(n)代入n代入方程r(n)，我們得到：
通過選擇a_0(n) = f(d(n))，a_1(n) = a_0(d(n)) = f(d(d(n)))，等：a_k(n) = f(d(d(...d(n)...)))（與k+1件d在對方），我們得到了一個正確的解決方案。
因此，在一般情況下，溶液的形式r(n) = sum{i=0..infinity}(f(d[i](n)))，其中d[i](n)表示具有i數d函數的迭代函數d(d(...d(n)...))的。
對於您的情況，d(n)=n/2和f(n)=n^2，因此您可以通過使用幾何級數的標識來獲得封閉形式的解決方案。最終結果是r(n)=4/3*n^2。
去提前主定理。
T(n) = aT(n/b)+n^klog^p
where a>0 b>1 k>0 p=real number.
case 1: a>b^k
T(n) = 0(n^logba) b is in base.
case 2 a=b^k
1. p>-1 T(n) than T(n)=0(n^logba log^p+1)
2. p=-1 Than T(n)=0(n^logba logn)
3. p<-1 than T(n)=0(n^logba)
case 3: a<b^k
1.if p>=0 than T(n)=0(n^k log^p n)
2 if p<0 than T(n)=O(n^k)
原諒常量bcoz恆定不改變時間複雜度或恆定變化處理器處理器（即，n/2 == N */2 == N）
這個問題似乎會偏離因爲它是關於Math，它屬於[Math.SE] – ja72