1

这是我的递归函数：

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

4

1 回答 1

3

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

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

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

如果n == 0thenn/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。

主定理提供关于 的渐近界的信息T(n)，具体取决于 和 的复杂f(n)性。这取决于如何使用采用(log with base b of a)的形式来表达的复杂性。0 的对数未定义，b > 0。abf(n)logb(a)

归结为，询问主定理是否适用于某些特定输入是没有意义的。此外，主定理无论如何都成立，它只是指出，取决于f(n)你可以对复杂性T或不复杂性做出一些声明。这取决于aand 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)（请注意此处的欧米茄），那么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)，这应该是正确的。

于 2017-04-20T08:18:33.833 回答