2.分治算法
2021/10/5 20:11:17
本文主要是介绍2.分治算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
分治算法思想
分治算法使用条件
二分搜索
分治算法之快速排序
分治算法思想
思想:规模为n的原问题的解无法直接求出,进行问题规模缩减,划分子问题(这里子问题相互独立和原问题解的性质是相同的,只是问题规模缩小了)。如果子问题的规模仍然不够小,再进行子问题划分,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止,最后将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。
分治算法使用条件
分治算法所能解决的问题一般具有以下几个特征:
- 原问题的规模小到一定的程度就可以容易地解决
- 原问题可以分解为若干个规模较小的相同问题。即原问题具有最优子结构性质
- 利用原问题分解出的子问题的解可以合并为原问题的解
- 原问题所分解出的各个子问题是相互独立的。即子问题之间不包含公共子问题(这条特征涉及到分治算法的效率,如果各个子问题不独立也就是子问题划分有重合的部分,则分治算法要重复的求解公共子问题的解,此时虽也可用分治算法,但是采用动态规划更好)
二分搜索
每次查找中间元素,从中间元素分开成二叉树,递归依次找到最后一个节点
代码实现:
#include <stdio.h> #include <stdlib.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; bool binarySearch(vector<int> &vec, int i, int j, int val) { if (i > j) { return false; //元素不存在; } int mid = (i + j) / 2; if (vec[mid] == val) { return true; } else if (vec[mid] > val) { return binarySearch(vec, i, mid - 1, val); } else { return binarySearch(vec, mid + 1, j, val); } } int main() { vector <int> vec; for (int i = 0; i < 11; ++i) { vec.push_back(rand() % 100); } sort(vec.begin(), vec.end()); for (int v : vec) { cout << v << " "; } cout << endl; bool result = binarySearch(vec, 0, vec.size() - 1, 58); cout << "result : " << result << endl; system("pause"); return 0; }
结果如图:
分治算法之快速排序
见文章交换排序中的快排交换排序 (冒泡排序和快速排序)_xiaoming1999的博客-CSDN博客
这篇关于2.分治算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-29P标签教程:初学者必备指南
- 2024-09-29PS网页切图教程:新手必学的网页设计技巧
- 2024-09-29简单易懂的Web布局教程
- 2024-09-29Web网页开发教程:从零开始的简单入门指南
- 2024-09-298D项目实战:新手入门教程
- 2024-09-29变形项目实战:新手必备入门指南
- 2024-09-29弹性盒子布局项目实战:从入门到上手
- 2024-09-29点击加载项目实战:新手入门必读教程
- 2024-09-29电商网页开发项目实战:新手入门教程
- 2024-09-29封装项目实战:从入门到初级应用