掌握定理和递归

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

您可以通过更改变量来“作弊”。

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

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

我们重写

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

通过的Master定理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).