归并排序递归树：分与合一眼看懂
用递归树拆解归并排序：每层代价恒为 n，叠 log₂n 层得 Θ(n log n)。
归并排序的“分”把数组对半切到单元素（天然有序），“合”再自底向上合并。下面用递归树看清每一层的代价。
图：归并排序的“分—合”递归结构（以 [5,2,4,6,1,3,2,8] 为例）
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
每层子问题规模之和为 n，合并总代价 Θ(n)；树高 log₂n，故总代价 Θ(n log n)。这与主定理结论一致。
评论 (0)
正文划词可点「问萝卜特」——自动发评论并由 AI 回复
加载评论中…