计算嵌套循环代码时间复杂度：log(n-1)!如何简化为big-O形式？

初始推导正确性验证 #

你给出的求和式是完全正确的：
内层循环的终止条件是j > 0，每次迭代j的值折半，因此对于任意正整数i，内层循环的执行次数为⌊log₂i⌋ + 1，忽略常数项和向下取整的影响后，单次外层循环的时间开销为O(log i)。
外层循环i从0到n-1，i=0时内层循环不执行，因此总时间开销的求和式确实为：
log₂1 + log₂2 + log₂3 + ... + log₂(n-1) = log₂((n-1)!)

求和式的大O简化 #

这里可以通过斯特林近似公式或者放缩法推导量级：

方法1：斯特林近似公式 #

斯特林公式给出阶乘的渐近近似：
n! ≈ √(2πn) * (n/e)^n
两边取对数可得：
log₂(n!) ≈ log₂(√(2πn)) + n*log₂(n/e) = n log₂n - n log₂e + (1/2)log₂(2πn)
忽略低阶项后，可得log₂(n!) = Θ(n log n)，同理log₂((n-1)!)和log₂(n!)是同量级的，因此可以直接简化为O(n log n)。

方法2：不等式放缩（无需记忆斯特林公式） #

我们可以直接对求和式做上界放缩：

sum_{i=1}^{n-1} log i ≤ sum_{i=1}^{n-1} log(n-1) = (n-1)log(n-1) = O(n log n)

如果要验证紧下界也可以做如下放缩：

sum_{i=1}^{n-1} log i ≥ sum_{i=⌊n/2⌋}^{n-1} log i ≥ sum_{i=⌊n/2⌋}^{n-1} log(⌊n/2⌋) ≥ (n/2) log(n/2) = Ω(n log n)

上下界同量级，因此该求和式的紧渐近界为Θ(n log n)，对应的大O表示就是O(n log n)。

最终结论 #

你给出的这段C语言代码的时间复杂度为O(n log n)。

内容的提问来源于stack exchange，提问作者BigC