我想证明为什么拉普拉斯行列式或递归算法的复杂度是n!。任何人都可以为我证明吗？我不知道它怎么会是 n!，因为等式 T(n)=nT(n-1)+3n-1 只涉及乘法和添加。
最佳答案
尝试展开:
T(n) = n T(n-1) + 3n-1 =
n ((n-1)T(n-2) + 3(n-1)-1) + 3n-1 =
n (n-1) T(n-2) + 3 n (n-1) - n + (3n - 1)
现在通过归纳你可以证明(如果 T(1) = 1):
T(n) = n (n-1) (n-2) ... 1 + 3(n + n (n-1) + ... + n!) -
(1 + n + n (n-1) + ... + n (n-1) ... n * (n-1) * ... * (n-2))
= Theta(n!)
关于algorithm - 证明递归行列式的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58520395/