这是我的递归函数：
function abc(n):
if n == 0
return xyz(n)
for i = 1 to n
print(xyz(n))
return abc(n/2) + abc(n/2)
而xyz（）是_（n^3）。主定理在这里有效吗？如果，是的，我怎么写？
最佳答案
主定理涉及这种形式的递推关系：
t（n）=a*t（n/b）+f（n）
T是递归过程，a我们将输入划分成的子问题的数目，n每个子问题的大小，f（n）将输入划分成子问题的成本和结果的组合。
如果n/b则n == 0变为0，n/b也变为0。这就留给我们：
T（0）=0+f（0）
由于不再有递归，它基本上可以归结为a。在你假设的情况下，这有一个复杂度（n ^ 3）。
由于f(0)是将f(n)划分为n子问题的成本，并且是结果的组合，a的成本通常为0或常数如果函数f(0)具有复杂性（n ^ 3），那么实际上对于f(n)这仍然导致输入大小的0的成本。
主定理提供了关于的渐近界的信息，这取决于n == 0、T(n)和f(n)的复杂性。这取决于如何使用一个使用a的窗体来表示b的复杂性（日志带有A的基B）。0的日志未定义为b>0。
归根结底，问主定理是否适用于某些特定的输入是没有意义的此外，主定理仍然成立，它只是说，根据f(n)可以对“cc>”的复杂性作出一些声明。这取决于logb(a)和f(n)，因此如果没有这些信息，询问是毫无意义的。如果您的T在基本情况之外也有O（n^3）（n>0），那么您可以根据这3与a和b的关系来声明T例如，如果f(n)您将确保t是_（n^（logb（a））。
假设你的算法中的a是b，那么主定理不能再用来说明T的复杂性。
编辑
在问题编辑之后，递归过程的形式变为：
T（n）=2*T（n/2）+f（n）
因此3 < logb(a)和a是本例中的参数，因为您将输入分为两个子问题，每个子问题得到的输入是执行递归的输入的一半。两个递归调用的组合是常数（简单的加法运算），对问题的划分也很简单，但在您的例子中，这一部分可以模拟将输入划分为子问题的_（n^4）算法：
for i = 1 to n
print(xyz(n))
注意它是_（n^4），因为您声明2^n是_（n^3），并且在循环中重复n次。所以你的a == 2。
主定理不能说明这一点。但是，如果b == 2（注意这里的ω），则abc(n/2) + abc(n/2)（在您的情况下为b=2和a=2的logb（a））。为了说明T的复杂性，另一个条件现在必须保持，正则性条件。它指出对于某些k<1和足够大的n，xyz(n)必须是真的。
这就给了我们f(n) = ϴ(n^4)k<1/8时也是如此。最后，这让我们声明f(n) = Ω(n^4)，所以4 > log2(2)。
也就是说，如果你的f（n）（带xyz调用的循环）被证明是Ω（n^4）（同样，注意ω而不是θ），那么最后一部分是真的。因为ω是下界，而f（n）=_（n^4），这应该是真的。