我对于简化这种复发关系感到困惑：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