algorithm - 算法的时间复杂度是多少？

Question

这是算法教科书中的一个问题，我认为时间复杂度是 log(n!)，但我的同学说它是 nlog(n)。非常感谢您的回复！！

count ← 0
for i ← 1 to n do
    j ← ⌊n/2⌋
    while j ≥ 1 do
        count ← count + 1
        if j is odd then
           j←0
        else
           j ← j/2
        end if
    end while
 end for

Answer 1

我认为时间复杂度是log(n!)，但我同学说是nlog(n)。

你俩都是对的。从斯特林公式可以看出，

log n! = n * log n - n +O(log(n)),

（log这里是自然对数）更准确地说：

log n! = (n + 1/2) * log n - n + 1/2 * log (2π) + O(1/n)

所以O(log n!)和O(n*log n)是同一类。

Answer 2

取最坏情况，n = 2 ^p

• 循环 1 到 n
• 对于每个循环，将j除以 2 直到它 < 1

所以，n * log₂(n)次迭代，或时间复杂度O(n log(n))

--

（根据评论，日志基数在复杂性上不是必需的，因为log ₂ (x)实际上是log(x)/log(2)即log(x) 乘以常数）