algorithm - 如果基本情况不是在恒定运行时而是在多项式运行时运行，那么主定理是否适用？

Question

这是我的递归函数:

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)。大师定理在这里有效吗？如果是，我将如何写？

Answer 1

主定理涉及这种形式的递归关系:

T(n) = a * T(n/b) + f(n)

T作为递归过程，a我们将输入分成的子问题数量 n , n/b每个子问题的大小和 `f(n) 将输入划分为子问题和结果组合的成本。

如果n == 0然后 n/b变为 0，a 也变为 0 .这给我们留下了:

T(0) = 0 + f(0)

由于不再有递归，它基本上归结为 f(0) .在您的假设情况下，这具有复杂性 ϴ(n^3)。

自 f(n)是 n 的除法成本进入a子问题和结果的组合，f(0)通常成本为 0 或常数。如果函数f(n)复杂度为 ϴ(n^3)，那么实际上是 n == 0这仍然导致输入大小的成本为 0。

主定理提供了关于 T(n) 的渐近界的信息，取决于 f(n) 的复杂性, a和 b .这取决于f(n)的复杂程度如何可以使用采用 logb(a) 的形式表示(以 a 的 b 为底记录)。 0 的对数未定义，b > 0。

归根结底，询问主定理是否适用于某些特定输入是没有意义的。此外，主定理无论如何都成立，它只是说明取决于f(n)。你可以对 T 的复杂性做出一些声明或不。这取决于 a和 b ，所以如果没有这些信息，询问是没有意义的。如果你的f(n)在基本情况之外也有 O(n^3) (n > 0) 那么你可以根据 3 与 a 的关系来声明 T和 b .例如，如果 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) (在您的情况下，logb(a) 与 b = 2 和 a = 2)。为了对 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)，那应该是正确的。