主定理和循环

Question

我想了解如何解决此代码的主定理：

unsigned long fac (unsigned long n ) {
    if (n == 1 )
        return 1;
    else
        return fact(n-1)*n;
}

所以基于我只有1次调用自己a=1的事实。除了那个函数调用之外，没有别的，所以 O(n) = 1 也是如此。现在我正在为我的b而苦苦挣扎。通常通用公式为：

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

在这种情况下，我不划分主要问题。新问题只需解决 n-1。 b 现在是什么？ 因为我的重现是：

T(n) = 1*T(n-1) + O(1)

我现在如何使用大师定理，因为我不知道我的确切 b？

Answer 1

大定理不适用于这个特定的递归关系，但这没关系 - 它不应该适用于所有地方。您最常看到主定理出现在分而治之的循环中，您将输入分成块，这些块是输入原始大小的恒定分数，而在这种特殊情况下，情况并非如此。

要解决此递归问题，您需要使用其他方法，例如迭代法或以不同方式查看递归树的形状。

Answer 2

你可以"cheat"通过改变变量。

让T(n) = S(2^n)。然后重复说

S(2^n) = S(2^n/2) + O(1)

我们重写

S(m) = S(m/2) + O(1).

根据大师定理a=1, b=2，解是对数

S(m) = O(log m),

这意味着

T(n) = S(2^n) = O(log 2^n) = O(n).

反正递归比较好直接解决，用

T(n) = T(n-1) + O(1) = T(n-2) + O(1) + O(1) = ... = T(0) + O(1) + O(1) + ... O(1) = O(n).

Master Theorem & Recurrences