hello算法之分治
分治
分治(divide and conquer),全称分而治之,是一种非常重要且常见的算法。分治通常基于递归实现,包括“分”和“治”两个步骤。
- 分(划分阶段):递归地将原问题分解为两个或多个子问题,直至到达最小子问题时终止。
- 治(合并阶段):从已知的最小子问题开始,从底至顶地将子问题的解进行合并,从而构建出原问题的解。
归并排序是分治策略的典型应用之一。
- 分:递归的将原数组分化成两个子数组,直到每个数组只剩一个元素。
- 治:从底至顶地将有序的子数组进行合并,从而得到一个有序的原数组。
如何判断分治问题
一个问题是否合适用分治来解决,通常有以下的几个判断标准。
- 问题可以分解:原问题可以分解成规模更小的,类似的子问题,以及能够以相同的方式递归进行划分。
- 子问题是独立的:子问题之间没有重叠,互不依赖,可以独立解决。
- 子问题的解可以合并:原问题的解通过合并子问题的解来合并。
显然,归并排序满足以上三点。
- 问题可以分解:递归地将原数组划分为两个子数组。
- 子问题是独立的:每个子数组都可以独立地进行排序。
- 子问题的解可以合并:两个有序数组可以合并为一个有序数组。
通过分治提升效率
分治不仅可以有效解决算法问题,往往还可以提升算法效率。在排序算法中,快速排序、归并排序、堆排序相较于选择、冒泡、插入排序更快,就是因为他们应用了分治策略。
那么,我们不禁发问:为什么分治可以提升算法效率,其底层逻辑是什么?换句话说,将大问题分解为多个子问题、解决子问题、将子问题的解合并为原问题的解,这几步的效率为什么比直接解决原问题的效率更高?这个问题可以从操作数量和并行计算两个方面来讨论。
1.操作数量优化
以冒泡排序为例,其处理一个长度为n的数组需要O(n^2)时间。假设我们按照下面的方式进行。将数组从中点处分为两个子数组,则划分需要O(n)的时间,排序每个子数组需要O((n/2)^2)时间,合并两个子数组需要O(n)时间,总体时间复杂度为O((n^2/2)+2n)
2.并行计算优化
我们知道,分治生成的子问题是相互独立的,因此通常可以并行解决。也就是说,分治不仅可以降低算法的时间复杂度,还可以利用操作系统的并行优化。
并行优化在多核或多处理器的环境中尤其有效,因为系统可以同时处理多个子任务,更加充分地利用计算资源,从而显著降低总体的运行时间。
分治搜索策略
之前已经研究过了,搜索算法的两大类。
- 暴力搜索:它通过遍历数据结构实现,时间复杂度为O(n)。
- 自适应搜索:它利用特有的数据组织形式或先验证信息,时间复杂度可达O(log n)甚至O(1)
实际上,时间复杂度为O(log n)的搜索算法通常是基于分治策略实现的,例如二分查找树。
- 二分查找的每一步都将问题分解为一个小问题,这个过程一直持续到数组为空或者找到目标元素为止。
- 数是分治思想的代表,在搜索二叉树、AVL树、堆等数据结构中,各种操作的时间复杂度皆为O(log n)。
二分查找的分治策略如下。
- 问题可以分解: 二分查找递归地还原问题,分解为子问题。
- 子问题是独立的: 在二分查找中,每一轮只处理一个子问题,它不受其他子问题的影响。
- 子问题的解无需合并: 二分查找在查找一个特定元素,因此不需要将子问题的解进行合并。当子问题得到解决时,原问题也会同时得到解决。
分治能够提升搜索效率,本质是因为暴力搜索每轮只能排除一个选项,而分治搜索每轮可以排除一半选项。
基于分治实现二分查找
在之前的章节中,二分查找是基于递推(迭代)实现的。现在我们基于分治(递归)来实现。
int dfs(vector<int> &nums, int target, int i, int j) {
if(i > j) {
return -1;
}
int m = (i+j) / 2;
if(nums[m] < target) {
return dfs(nums, target, m+1, j);
}else if (nums[m] > target) {
return dfs(nums, target, i, m-1)
}else {
return m;
}
}
int binarySearch(vector<int> &nums, int target) {
int n = nums.size();
return dfs(nums, target, 0, n - 1);
}
构建二叉树问题
判断是否为分治问题
原问题定义为从preorder和inorder构建二叉树,是一个典型的分治问题。
- 问题可以分解
- 子问题上独立的
- 子问题的解可以合并
如何划分子树
根据以上分析,这道题可以使用分治来求解,但如何通过前序遍历preorder和中序遍历inorder来划分左子树和右子树呢?
根据定义,preorder和inorder都可以划分为三个部分。
- 前序遍历:
[ 根节点 | 左子树 | 右子树 ] - 中序遍历:
[ 左子树 | 根节点 | 右子树 ]
TreeNode *dfs(vector<int> &preorder, unordered_map<int, int> &inorderMap, int i, int l, int r) {
if(r - l < 0)
return NULL;
TreeNode *root = new TreeNode(preorder[i]);
int m = inorderMap[preorder[i]];
root->left = dfs(preorder, inorderMap, i+1, l, m-1);
root->right = dfs(preorder, inorderMap, i+1+m-l, m+1, r);
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
unordered_map<int, int> inorderMap;
for(int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorder.size() - 1);
return root;
}
汉诺塔问题
在归并排序和构建二叉树中,我们都是将原问题分解为两个规模为原问题一半的子问题。然而对于汉诺塔问题,我们采用不同的分解策略
/* 移动一个圆盘 */
void move(vector<int> &src, vector<int> &tar) {
int pan = src.back();
src.pop_back();
tar.push_back(pan);
}
void dfs(int i, vector<int> &src, vector<int> &buf, vector<int> &tar) {
if(i == 1) {
move(src, tar);
return;
}
dfs(i - 1, src, tar, buf);
move(src, tar);
dfs(i - 1, buf, src, tar);
}
void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
int n = A.size();
dfs(n, A, B, C);
}
