如果基本情况不是 运行 在常数运行时而是在多项式运行时，那么主定理是否适用？
Will master theorem be applicable if the base case is not running in constant runtime but in polynomial runtime?
这是我的递归函数：
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，n/b 每个子问题的大小和`f( n) 将输入划分为子问题和结果组合的成本。
如果n == 0则n/b变为0，a也是如此。这给我们留下了：
T(0) = 0 + f(0)
由于没有更多的递归，它基本上归结为f(0)。在您的假设情况下，这具有复杂性 ϴ(n^3).
由于 f(n) 是将 n 划分为 a 子问题和结果组合的成本，因此 f(0) 通常的成本为 0 或持续的。如果函数 f(n) 的复杂度为 ϴ(n^3)，那么实际上对于 n == 0 这仍然会导致输入大小的成本为 0。
主定理根据 f(n)、a 和 b 的复杂性提供有关 T(n) 渐近边界的信息。这取决于 f(n) 的复杂性如何使用采用 logb(a)（以 a 的 b 为底的日志）的形式来表达。 0 的对数未定义，b > 0。
归根结底，询问主定理是否适用于某些特定输入是没有意义的。此外，主定理无论如何都成立，它只是说明根据 f(n) 你可以对 T 的复杂性做出一些断言。这取决于 a 和 b，因此如果没有这些信息，询问是毫无意义的。如果您的 f(n) 在基本情况之外也有 O(n^3) (n > 0)，那么您可以根据 3 与 a 和 [=28= 的关系来声明 T ].例如，如果 3 < logb(a) 你会确定 T 是 ϴ(n^(logb(a)).
假设你的算法中的 a 是 2^n，那么主定理就不能再用来说明 T 的复杂性了。
编辑
你的问题编辑后，你的递归过程的形式变成了这样：
T(n) = 2 * T(n/2) + f(n)
所以 a == 2 和 b == 2 是您案例中的参数，因为您将输入分成两个子问题，每个子问题的输入都是递归输入的一半。两个递归调用的组合是恒定的（一个简单的加法abc(n/2) + abc(n/2)）并且问题的划分也很简单，但是你的这部分可以模拟一个 ϴ(n^4) 算法来将输入划分为子问题：
for i = 1 to n
print(xyz(n))
请注意它是 ϴ(n^4) 因为你说 xyz(n) 是 ϴ(n^3) 并且你在循环中重复它 n 次。所以你的 f(n) = ϴ(n^4).
主定理无法真正说明这一点。但是，如果 f(n) = Ω(n^4) （请注意此处的 omega），则 4 > log2(2) （在您的情况下为 b = 2 和 a = 2 的 logb(a) ）。为了说明 T 的复杂性，现在必须满足另一个条件，即 正则性条件 。它指出 a * f(n/b) <= k * f(n) 对于某些 k < 1 和足够大的 n 必须为真。
所以这给了我们 2 * f(n/2) <= k * f(n)。这适用于 k < 1/8。最后，让我们声明 T = ϴ(f(n))，所以 T = ϴ(n^4).
意味着如果您的 f(n)（带有 xyz 调用的循环）可以被证明为 Ω(n^4)（再次注意 omega 而不是 theta），则最后部分为真。由于 omega 是下限，而您的 f(n) = ϴ(n^4)，那应该是正确的。
这是我的递归函数：
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，n/b 每个子问题的大小和`f( n) 将输入划分为子问题和结果组合的成本。
如果n == 0则n/b变为0，a也是如此。这给我们留下了：
T(0) = 0 + f(0)
由于没有更多的递归，它基本上归结为f(0)。在您的假设情况下，这具有复杂性 ϴ(n^3).
由于 f(n) 是将 n 划分为 a 子问题和结果组合的成本，因此 f(0) 通常的成本为 0 或持续的。如果函数 f(n) 的复杂度为 ϴ(n^3)，那么实际上对于 n == 0 这仍然会导致输入大小的成本为 0。
主定理根据 f(n)、a 和 b 的复杂性提供有关 T(n) 渐近边界的信息。这取决于 f(n) 的复杂性如何使用采用 logb(a)（以 a 的 b 为底的日志）的形式来表达。 0 的对数未定义，b > 0。
归根结底，询问主定理是否适用于某些特定输入是没有意义的。此外，主定理无论如何都成立，它只是说明根据 f(n) 你可以对 T 的复杂性做出一些断言。这取决于 a 和 b，因此如果没有这些信息，询问是毫无意义的。如果您的 f(n) 在基本情况之外也有 O(n^3) (n > 0)，那么您可以根据 3 与 a 和 [=28= 的关系来声明 T ].例如，如果 3 < logb(a) 你会确定 T 是 ϴ(n^(logb(a)).
假设你的算法中的 a 是 2^n，那么主定理就不能再用来说明 T 的复杂性了。
编辑
你的问题编辑后，你的递归过程的形式变成了这样：
T(n) = 2 * T(n/2) + f(n)
所以 a == 2 和 b == 2 是您案例中的参数，因为您将输入分成两个子问题，每个子问题的输入都是递归输入的一半。两个递归调用的组合是恒定的（一个简单的加法abc(n/2) + abc(n/2)）并且问题的划分也很简单，但是你的这部分可以模拟一个 ϴ(n^4) 算法来将输入划分为子问题：
for i = 1 to n
print(xyz(n))
请注意它是 ϴ(n^4) 因为你说 xyz(n) 是 ϴ(n^3) 并且你在循环中重复它 n 次。所以你的 f(n) = ϴ(n^4).
主定理无法真正说明这一点。但是，如果 f(n) = Ω(n^4) （请注意此处的 omega），则 4 > log2(2) （在您的情况下为 b = 2 和 a = 2 的 logb(a) ）。为了说明 T 的复杂性，现在必须满足另一个条件，即 正则性条件 。它指出 a * f(n/b) <= k * f(n) 对于某些 k < 1 和足够大的 n 必须为真。
所以这给了我们 2 * f(n/2) <= k * f(n)。这适用于 k < 1/8。最后，让我们声明 T = ϴ(f(n))，所以 T = ϴ(n^4).
意味着如果您的 f(n)（带有 xyz 调用的循环）可以被证明为 Ω(n^4)（再次注意 omega 而不是 theta），则最后部分为真。由于 omega 是下限，而您的 f(n) = ϴ(n^4)，那应该是正确的。