T(n) = n⋅log(n) + T(n-1) 的时间复杂度是多少？

Question

假设T(n) = n⋅log(n) + T(n-1)，那么T(n)的时间复杂度是多少?

Answer 1

T(n) = n log n + (n-1) log (n-1) + ... + 1 log 1 + T(0)
     < n log n + (n-1) log n + ... 1 log n + T(0)
     = ( n + n-1 + n-2 + ... + 1) log n + T(0)
     = n(n+1)/2 ⋅ log n + T(0)

如果T(0)也在O(n² log n)中，那么它在O(n² log n)中。

其他方式:

T(n) = n log n + (n-1) log (n-1) + ... + 1 log 1 + T(0)
     < n log n + n log (n-1) + ... + n log 1 + T(0)
     = n (log n + log (n-1) + ... + log 1) + T(0)
     = n log (n!) + T(0)
     < n log (nⁿ) + T(0)
     = n ⋅ n ⋅ log n + T(0)
     = n² log n

编辑:

你也可以用同样的方式看到一个下界:

T(n) = n log n + (n-1) log (n-1) + ... + 1 log 1 + T(0)
     > n log n/2 + (n-1) log n/2 + ... + n/2 log n/2 + (n/2-1) log 1 + ... 1 log 1 + T(0)
     = ( n(n+1)/2-n/4(n/2+1) ) log n/2 + T(0)
     = (3/8 n² + 1/4 n) log n/2 + T(0)
     = (3/8 n² + 1/4 n) log n - (3/8 n² + 1/4 n) log 2
     = 3/8 n² log n + 1/4 n log n - (3/8 n² + 1/4 n) log 2

所以T(n)在Ω(n² log n)里

加起来就是Θ(n² log n)(只要T(0)在O(n² log n)中)

Answer 2

展开为

T(n) = T(0) + 1⋅log(1) + 2⋅log(2) + ... + (n-1)⋅log (n-1) + n⋅log(n)

≈ ∫n⋅log(n) dn = (n²/2)⋅log(n)−n²/4 = O(n²⋅logn)

(使用积分逼近)

Answer 3

将T(n)表示为一个和，那么解马上就出来了。