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), 并且用于创建阶乘的所有值都是平方的。

Answer 2

如果我们用零替换 3（这显然不会改变 Θ），我们可以很容易地推导出函数调用的确切数量：

Θ _{f ( 1 )} = 1
Θ _{f ( n )} = n ² ⋅ Θ _{f ( n -1 )}         ∀ n > 0

因此，利用产品的交换性，

                  _n                  <sub> n           _n
Θ _{f ( n )} = ∏   j ²   = ∏ j   ⋅ ∏ j   =  n！⋅ n！
               <em>i =1 <em>i =1 <em>i =1
= ( n !) ²

正如杰森所说。