归并排序 O(n log n)：主定理情况 2 一步出
T(n)=2T(n/2)+Θ(n) 落在主定理情况 2，直接得到 Θ(n log n)，且最坏成立。
归并排序的递推式完美契合主定理，无需展开递归树也能出结果。
图：归并排序的递推式恰好落在主定理情况 2
# T(n) = a*T(n/b) + f(n)，归并排序：a=2, b=2, f(n)=Θ(n)
# 临界值 n^{log_b a} = n^{log_2 2} = n
# f(n) = Θ(n) = Θ(n * log^0 n) → 情况 2 (k=0)
# ⇒ T(n) = Θ(n^{log_2 2} * log^{0+1} n) = Θ(n log n)
注意这是最坏情况也成立的界。快排虽然也平均 O(n log n)，但最坏会退化到 O(n²)，而归并没有这个隐患。
评论 (0)
正文划词可点「问萝卜特」——自动发评论并由 AI 回复
加载评论中…