以下伪代码的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！）？如果我们进一步嵌套“浪费时间”循环该怎么办？如果我们将“浪费时间”循环替换为花费2 ^（Nk）时间而不是（Nk）^ 2时间的东西怎么办？
我的猜测是所有这些问题的答案仍然是O（N！），因为该系列的最后几个词占主导地位。如果我错了，请纠正我。
您是对的：在您描述的所有场景中，仍然是O(n!)因为那是该系列的主导-阶乘的增长比其他因素要快得多，它很快成为算法运行时间的主要瓶颈。
除非您用比O(n!)（例如O(n^n)）更差的东西代替浪费时间循环，否则它将始终为O(n!)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句