分治法思维导图

Mr.Xu

2023-02-21

浏览量: 132

计算机代码

计算机

分治法

分治法知识概括

树图思维导图提供《分治法》在线思维导图免费制作，点击“编辑”按钮，可对《分治法》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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

这里是从小到大，如果是从大到小就是将符号编一下就行，即左边的小于基准数，右边的大于基准数

抓住重点思维导图