为什么 O(log(n)) 等于 O(log(n!))？

Question

在解决一个代码的复杂度时，我发现它是O(log(n!))。我知道这可以证明等于 O(n*log(n))。但是，有人可以告诉这个证明哪里出了问题吗？

Theorems used:

log(ab) = log(a) + log(b)
O(a+b) = O(最大(a,b))

Proof

O(log(n!)) = O(log(n*(n-1)*(n-2)*...*2*1))

           = O(log(n) + log(n-1) + ... )

           = O(max(logn, log(n-1), ...))

           = O(log(n))

谁能告诉我哪里错了？

Answer 1

你不能说 O(log(n) + log(n-1) + ... ) = O(最大(logn, log(n-1), ...))

这仅适用于固定数量的加数。在您的情况下，数字取决于 n.

否则你也可以证明

O(n)=O(1+1+1+1+1+...1) = O(max(1,1,1,...))= O(1)

为什么 O(log(n)) 等于 O(log(n!))？

Why is O(log(n)) coming equal to O(log(n!))?

algorithm

complexity-theory

big-o

time-complexity