分治法思维导图
分治法知识概括
树图思维导图提供 分治法 在线思维导图免费制作，点击“编辑”按钮，可对 分治法 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：d055425fad67c5064885fe3efc8f3ccb
思维导图大纲
分治法思维导图模板大纲
含义
就是分而治之，将一个大问题分成若干个子问题，再把子问题更小的子问题，直到最后子问题可以直接求解，原问题的解即子问题解的合并，其中每个子问题的解是独立互不影响的
实现方法
分
递归解决较小的问题（到终止层或可以直接解决的时候停下）
治
递归求解，如果问题够小直接求解
精髓
分
将大问题分解为规模更小的子问题
治
将这些子问题逐个击破
合
将已解决的子问题合并，最终得出大问题的解
实际操做
确定初始条件
要规定边界，避免无限制的分解下去
计算时间复杂度
分
假设划分问题为a个子问题，每个子问题大小为n/b,则时间复杂度为D(n),即是关于n的函数
治
每个子问题与原问题性质一致，原问题大小为n，时间复杂度为T(n)，则子问题大小为n/b，时间复杂度为T(n/b)，有a个子问题，所以总时间复杂度是aT(n/b)
合
即将所有子问题的时间复杂度合并起来，共有a个子问题，所以合并的过程时间复杂度也是n的函数假设时间复杂度为C(n)
合并时间复杂度
T(n)=D(n)+aT(n)+C(n)
求解
......
与递归的区别
分治是一种思想，递归是一种方法工具，这种方法通过调用自己形成一个来回的过程，而分治就是利用了多次这样来回的过程
课堂例题
题目
输入n个数，将这n个数从小到大排序
思路
将这n个数分成2个部分，找一个基准数，将左右两边的数与基准数进行比较，如果左边的大于基准数且右边的小于基准数，就将两个数进行交换，再将基准数左右两边各自继续排序，以此类推，最后分解到a[1],a[n]是停止
代码
#include<bits/stdc++.h> using namespace std; int a[50005]; void qs(int l,int r){ int i=l,j=r; int mid=a[(l+r)/2]; while(i<=j){ while(a[i]<mid) i++; while(a[j]>mid) j--; if(i<=j){ swap(a[i],a[j]); i++; j--; } } if(l<j) qs(l,j); if(i<r) qs(i,r); } int main(){ int n; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); qs(1,n); for(int i=1;i<=n;i++) printf("%d ",a[i]); return 0; }
Tip
这里是从小到大，如果是从大到小就是将符号编一下就行，即左边的小于基准数，右边的大于基准数
沪公网安备 31011502019485号
上海工商