Big-O 运行递归函数的时间

Question

以下伪代码的Big-O运行时间是多少：

rec(int N) {
    if (N<0) return;
    for i=1:N {
        for j=1:N {
            print("waste time");
        }
        rec(N-1);
    } 
}

如果我的理解是正确的，这段代码的精确运行时间应该是

N^2 * 1 + (N-1)^2 * N + (N-2)^2 * N * (N-1) ... + N!

或等效

(N-k)^2 * nPk from k=0 to k=N-1

Big O 运行时还会是 O(N!) 吗？如果我们进一步嵌套 "waste time" 循环会怎样？如果我们用需要 2^(N-k) 时间而不是 (N-k)^2 时间的东西替换 "waste time" 循环会怎么样？

我的猜测是，所有这些问题的答案仍然是 O(N!)，因为该系列的最后几项占主导地位。如有错误请指正

Answer 1

你是对的：在你描述的所有场景中，它仍然是 O(n!) 因为这是主导该系列的因素 - 阶乘比其他因素增长得更快，它很快成为主要瓶颈在算法的运行时间内。

除非你用比 O(n!) 更糟糕的东西（例如 O(n^n)）替换浪费时间的循环，否则它将永远是 O(n!)。

Big-O running time of recursive function