2.分治算法

目录

分治算法思想

分治算法使用条件

二分搜索

 分治算法之快速排序


分治算法思想

思想:规模为n的原问题的解无法直接求出,进行问题规模缩减,划分子问题(这里子问题相互独立和原问题解的性质是相同的,只是问题规模缩小了)。如果子问题的规模仍然不够小,再进行子问题划分,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止,最后将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。

分治算法使用条件

分治算法所能解决的问题一般具有以下几个特征:

  1. 原问题的规模小到一定的程度就可以容易地解决
  2. 原问题可以分解为若干个规模较小的相同问题。即原问题具有最优子结构性质
  3. 利用原问题分解出的子问题的解可以合并为原问题的解
  4. 原问题所分解出的各个子问题是相互独立的。即子问题之间不包含公共子问题(这条特征涉及到分治算法的效率,如果各个子问题不独立也就是子问题划分有重合的部分,则分治算法要重复的求解公共子问题的解,此时虽也可用分治算法,但是采用动态规划更好)

二分搜索

   每次查找中间元素,从中间元素分开成二叉树,递归依次找到最后一个节点 

2.分治算法

 代码实现:

#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;
}

 结果如图:

2.分治算法

 分治算法之快速排序

见文章交换排序中的快排交换排序 (冒泡排序和快速排序)_xiaoming1999的博客-CSDN博客

上一篇:并查集板子


下一篇:分治算法—求大数的top k问题