c++ - 递归的 Theta 运行时间

Question

如何计算此给定代码的 Theta 运行时间:

void f(int n)
{
    for (int i=3; i<n; ++i)
        for (int j=0; j<i; ++j)
            f(n-1);
}

到目前为止我得到了这个，但我不知道它是否正确或如何将它引入 Theta 表示法。

f(n) = n^2 * f(n-1)
f(n) = n^2 * (n-1)^2 * f(n-2)
f(n) = n^2 * (n-1)^2 * (n-2)^2 * f(n-3) 
...

Answer 1

由于每个嵌套 for 循环的复杂度为 O(N^2)，并且每次在另一个函数中调用一个函数时，复杂度都会成倍增加，最终得到 O((N!)^2)，其中 N也是你递归的次数。这当然是因为 N! = N*(N-1)*(N-2)*...*(N-N+1)，所有用于创建阶乘的值均已平方。