如何证明递归式T(n)=T(n-1)+log n的复杂度为Θ(nlog n)

没问题，我来帮你把这个递归式的时间复杂度证明讲清楚，尤其是你关心的下界部分～

首先我们先把递归式展开，假设递归基 ( T(1) = C )（C是常数，不影响渐近复杂度），展开后可以得到：
[
T(n) = C + \sum_{k=2}^n \log k
]
要证明 ( T(n) = \Theta(n\log n) )，根据渐近符号的定义，我们需要分别证明上界 ( T(n) = O(n\log n) ) 和 下界 ( T(n) = \Omega(n\log n) )。

1. 上界证明（( O(n\log n) )） #

这部分确实比较直接：

• 对于所有 ( 2 \leq k \leq n )，显然 ( \log k \leq \log n )
• 所以求和式 ( \sum_{k=2}^n \log k \leq \sum_{k=2}^n \log n = (n-1)\log n )
• 当 ( n \geq 1 ) 时，( (n-1)\log n \leq n\log n )，因此 ( T(n) \leq C + n\log n = O(n\log n) )

2. 下界证明（( \Omega(n\log n) )） #

这是你重点关心的部分，我们可以通过拆分求和区间的方法来推导：

• 首先，我们只关注求和式的后半段：( \sum_{k=2}^n \log k \geq \sum_{k=\lceil n/2 \rceil}^n \log k )（因为前半段的和是非负的，去掉不影响下界）
• 对于区间 ( \lceil n/2 \rceil \leq k \leq n ) 里的每个k，都有 ( k \geq n/2 )，因此 ( \log k \geq \log(n/2) = \log n - \log 2 )（这里( \log 2 )是常数，约等于1）
• 这个区间里的项数至少是 ( n - \lceil n/2 \rceil + 1 )，当n足够大时，这个项数≥ ( n/2 )（比如n是偶数时，项数是( n/2 + 1 )；n是奇数时，项数是( (n+1)/2 )，都大于等于( n/2 )）
• 把这两个结论结合起来，求和式的下界可以写成：
  [
  \sum_{k=\lceil n/2 \rceil}^n \log k \geq \frac{n}{2} \times (\log n - \log 2)
  ]
• 整理一下这个式子：
  [
  \frac{n}{2}\log n - \frac{n}{2}\log 2
  ]
• 当n足够大时，( \frac{n}{2}\log 2 )相对于( \frac{n}{2}\log n )可以忽略，比如取n≥4时，( \log n \geq 2 )，此时( \frac{n}{2}\log 2 \leq \frac{n}{4}\log n )，因此：
  [
  \frac{n}{2}\log n - \frac{n}{2}\log 2 \geq \frac{n}{2}\log n - \frac{n}{4}\log n = \frac{n}{4}\log n
  ]
• 也就是说，存在常数( c = 1/4 )和( n_0 = 4 )，当( n \geq n_0 )时，( \sum_{k=2}^n \log k \geq c \cdot n\log n )，加上递归基的常数C，依然满足( T(n) = \Omega(n\log n) )

结论 #

因为我们同时证明了( T(n) = O(n\log n) )和( T(n) = \Omega(n\log n) )，根据( \Theta )符号的定义，就可以得出( T(n) = \Theta(n\log n) )。

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