归并排序时间复杂度O(nlogn)深度解析：以LeetCode 148.排序链表为例
归并排序时间复杂度O(nlogn)深度解析：以LeetCode 148.排序链表为例
一、引言
在刷LeetCode 148.排序链表时，很多同学会对归并排序的时间复杂度O(nlogn)感到困惑：为什么它一定能达到这个复杂度？分解和合并的过程具体是如何贡献这个复杂度的？本文将通过详细的图解和代码分析，揭开归并排序时间复杂度背后的数学原理。
二、问题背景：LeetCode 148.排序链表
题目要求对链表进行排序，进阶要求时间复杂度O(nlogn)且常数级空间复杂度。归并排序正是满足这一要求的经典解法。
示例：
- 输入：
4 → 2 → 1 → 3 - 输出：
1 → 2 → 3 → 4
三、归并排序的核心思想：分而治之
归并排序采用分治策略，将排序问题分解为三个步骤：
- 分解：将原问题分解成若干个规模较小的子问题
- 解决：递归地解决这些子问题
- 合并：将子问题的解合并成原问题的解
其时间复杂度可以用递归公式表示：
T(n) = 2T(n/2) + O(n) 其中：
- 2T(n/2)：分解成两个规模为n/2的子问题所需时间
- O(n)：合并两个有序子序列所需时间
四、为什么是O(nlogn)？从二叉树的角度理解
4.1 分解过程形成一棵"递归树"
以8个节点的链表为例：8 → 4 → 2 → 1 → 7 → 5 → 3 → 6
分解过程（递归地寻找中点）：
关键观察：
- 树的高度 = log₂n（8个节点需要log₂8=3层分解才能得到单个节点）
- 每层处理的节点总数始终为n（只是被分成了更小的子链表）
4.2 合并过程自底向上构建有序链表
从最底层的单个节点开始，逐层合并：
第4层（合并后）：[8] [4] → [4,8] [2] [1] → [1,2] [7] [5] → [5,7] [3] [6] → [3,6] \ / \ / 第3层（合并后）： [1,2,4,8] [3,5,6,7] \ / 第2层（合并后）： [1,2,3,4,5,6,7,8] 五、时间复杂度逐层剖析
5.1 分解阶段的工作量
在递归版本的代码中，分解阶段主要工作在searchMid函数：
publicListNodesearchMid(ListNode head){ListNode fast = head.next, slow = head;while(fast !=null&& fast.next !=null){ slow = slow.next; fast = fast.next.next;}return slow;// 返回中点}每层的工作量计算：
| 层数 | 子链表个数 | 每个子链表长度 | 每层总遍历次数 |
|---|---|---|---|
| 第1层 | 1 | n | n/2 |
| 第2层 | 2 | n/2 | 2 × (n/4) = n/2 |
| 第3层 | 4 | n/4 | 4 × (n/8) = n/2 |
| … | … | … | … |
| 第log n层 | n/2 | 2 | (n/2) × 1 ≈ n/2 |
结论：分解阶段每层的工作量都是O(n)，共有log n层，所以分解阶段总时间复杂度 = O(n) × O(log n) = O(n log n)
5.2 合并阶段的工作量
合并阶段的核心是mergeList函数：
publicListNodemergeList(ListNode head1,ListNode head2){ListNode h =newListNode();ListNode p = h;ListNode p1 = head1, p2 = head2;while(p1 !=null&& p2 !=null){if(p1.val <= p2.val){ p.next = p1; p1 = p1.next;}else{ p.next = p2; p2 = p2.next;} p = p.next;} p.next =(p1 ==null? p2 : p1);return h.next;}每层的工作量计算：
| 层数 | 合并的对数 | 每对合并的比较次数 | 每层总操作次数 |
|---|---|---|---|
| 第1层（自底向上） | 4对（n/2对） | 每对最多2次 | ≤ 4×2 = 8 ≈ n |
| 第2层 | 2对（n/4对） | 每对最多4次 | ≤ 2×4 = 8 ≈ n |
| 第3层 | 1对（n/8对） | 每对最多8次 | ≤ 1×8 = 8 ≈ n |
结论：合并阶段每层的工作量也都是O(n)，共有log n层，所以合并阶段总时间复杂度 = O(n) × O(log n) = O(n log n)
5.3 总时间复杂度
总时间复杂度 = 分解阶段 + 合并阶段 = O(n log n) + O(n log n) = O(2n log n) = O(n log n) （常数因子忽略） 六、两种实现方式的复杂度对比
6.1 递归实现（自顶向下）
classSolution{publicListNodesortList(ListNode head){if(head ==null|| head.next ==null)return head;ListNode slow =searchMid(head);// O(n)分解ListNode tmp = slow.next; slow.next =null;ListNode left =sortList(head);// T(n/2)ListNode right =sortList(tmp);// T(n/2)returnmergeList(left, right);// O(n)合并}}- 空间复杂度：O(log n)（递归调用栈）
6.2 迭代实现（自底向上）
classSolution{publicListNodesortList(ListNode head){// ...计算链表长度lengthfor(int subLength =1; subLength < length; subLength <<=1){// 每轮subLength翻倍，共log n轮ListNode cur = dummy.next;while(cur !=null){// 提取两个长度为subLength的子链表// 合并它们 O(n)// ...}}}}- 空间复杂度：O(1)（满足题目进阶要求）
七、与其他排序算法的对比
| 排序算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n)或O(log n) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
归并排序的最大优势：无论输入数据如何，都能保证O(n log n)的时间复杂度。
八、常见疑问解答
Q1：为什么分解阶段也算时间复杂度？不是只算合并吗？
A：分解阶段虽然不涉及元素比较，但需要遍历链表寻找中点（searchMid函数），这些遍历操作同样消耗时间，需要计入总时间复杂度。
Q2：为什么说是O(n log n)而不是O(n)？
A：因为需要log n层操作，每层都要处理n个元素。以8个元素为例，需要3层，每层处理8个元素，总操作次数约为24次（n log n），而不是8次（n）。
Q3：递归实现的空间复杂度为什么是O(log n)？
A：递归调用会使用系统栈，最深时递归log n层（因为每次规模减半），所以需要O(log n)的额外空间。
九、总结
归并排序O(n log n)的时间复杂度来源于其完美的分治结构：
- log n层：每次将问题规模减半，形成高度为log n的递归树
- 每层O(n)：无论是分解阶段的寻找中点，还是合并阶段的比较合并，每层都需要处理所有n个元素
- 层数 × 每层工作量 = O(log n) × O(n) = O(n log n)
这种"层数 × 每层工作量"的分析方法，不仅适用于归并排序，也是理解其他分治算法（如快速排序、二分查找）复杂度的核心思维模型。
十. 题解
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } *//** * 归并排序递归法 */classSolution{publicListNodesortList(ListNode head){if(head ==null|| head.next ==null){return head;}ListNode slow =searchMid(head);ListNode tmp = slow.next; slow.next =null;ListNode left =sortList(head);ListNode right =sortList(tmp);returnmergeList(left, right).next;}publicListNodesearchMid(ListNode head){ListNode fast = head.next, slow = head;while(fast !=null&& fast.next !=null){ slow = slow.next; fast = fast.next.next;}return slow;}publicListNodemergeList(ListNode head1,ListNode head2){ListNode h =newListNode();ListNode p = h;ListNode p1 = head1, p2 = head2;while(p1 !=null&& p2 !=null){if(p1.val <= p2.val){ p.next = p1; p1 = p1.next;}else{ p.next = p2; p2 = p2.next;} p = p.next;} p.next =(p1 ==null? p2 : p1);return h;}}/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } *//** * 自底向上的方法 */classSolution{publicListNodesortList(ListNode head){if(head ==null|| head.next ==null){return head;}int length =0;ListNode node = head;while(node !=null){ length++; node = node.next;}ListNode dummy =newListNode(0, head);for(int subLength =1; subLength < length; subLength <<=1){ListNode pre = dummy;ListNode cur = dummy.next;while(cur !=null){ListNode p1 = cur;for(int i =1; i < subLength && cur !=null&& cur.next !=null; i++){ cur = cur.next;}ListNode p2 = cur.next; cur.next =null; cur = p2;for(int i =1; i < subLength && cur !=null&& cur.next !=null; i++){ cur = cur.next;}ListNode next =null;if(cur !=null){ next = cur.next; cur.next =null;}ListNode mergeList =mergeTwoList(p1, p2); pre.next = mergeList;while(pre.next !=null){ pre = pre.next;} cur = next;}}return dummy.next;}publicListNodemergeTwoList(ListNode head1,ListNode head2){ListNode h =newListNode();ListNode p = h;ListNode p1 = head1, p2 = head2;while(p1 !=null&& p2 !=null){if(p1.val <= p2.val){ p.next = p1; p1 = p1.next;}else{ p.next = p2; p2 = p2.next;} p = p.next;} p.next =(p1 ==null? p2 : p1);return h.next;}}
