分治算法解题套路框架

分治算法解题套路框架

学习本文后，你将掌握分治算法的核心原理与解题套路，并能解决以下经典题目：

LeetCode题号	力扣题号	题目名称	难度
23	23	Merge k Sorted Lists（合并 K 个升序链表）	困难
21	21	Merge Two Sorted Lists（合并两个有序链表）	简单

前置知识

阅读本文前，建议先掌握：

• 二叉树的遍历框架
• 多叉树结构及遍历框架

一句话总结

分而治之的思想广泛存在于递归算法中，但并非所有问题用分治思想都能提升效率；仅当问题的求解复杂度为多项式级别时，分治思想才可能带来效率提升。

一、分治思想为何能提升效率？

通过完全平方公式可直观理解：
(a+b)2=a2+2ab+b2≥a2+b2(a+b)^2 = a^2 + 2ab + b^2 \ge a^2 + b^2(a+b)2=a2+2ab+b2≥a2+b2

假设原问题规模N=a+bN = a + bN=a+b，若直接用O(N2)O(N^2)O(N2)的算法求解，总时间复杂度为O((a+b)2)O((a+b)^2)O((a+b)