适合设计师看的设计网站,网页优化哪家公司做得好,上海专业做网站的公司有哪些,网站建设的公文格式算法中很多方法都是可以采用分治策略进行设计与优化#xff0c;那么什么是分治策略#xff1f;如何使用分治策略进行算法的设计与分析#xff1f; 文章目录1. 分治策略的基本思想1.1 二分检索的设计思想1.2 二分归并排序的设计思想1.3 Hanoi塔的递归算法2 小结1. 分治策略的… 算法中很多方法都是可以采用分治策略进行设计与优化那么什么是分治策略如何使用分治策略进行算法的设计与分析 文章目录1. 分治策略的基本思想1.1 二分检索的设计思想1.2 二分归并排序的设计思想1.3 Hanoi塔的递归算法2 小结1. 分治策略的基本思想
分治策略Divide and Conquer
将原始问题划分或归结为规模较小的子问题递归或者迭代的求解每个子问题将子问题的解综合得到原问题的解
在设计分治策略时一定要注意以下几点
子问题与原问题的性质完全一样子问题之间可以彼此独立的求解递归停止时子问题可以直接进行求解得出结果。
下面以二分检索的例子来分析分之策略的思想。
1.1 二分检索的设计思想
设算法Binary Search(Tlrx)。输入排好序的数组T 下标从l到r数x。输出j //若x在T中则为下标否则为0
给出下面的伪码 二分检索的设计思想
通过x与数组的中位数进行比较将原问题归结为规模减半的子问题。如果x小于中位数则子问题由小于x的数构成否则子问题由大于x的数构成。对子问题进行二分搜索算法当子问题为1时直接比较T[m]与x若相等则返回m否则返回0.
二分检索最坏情况下时间复杂度分析在前面的文章中已经学习了如何分析算法的时间复杂度如果不懂下面的公式的可以多看看前面的文章。
W(n)W(⌊n/2⌋)1W(n) W(\lfloor n/2 \rfloor)1W(n)W(⌊n/2⌋)1 W(1)1W(1) 1W(1)1
可以解出
W(n)⌊logn⌋1W(n) \lfloor logn \rfloor 1W(n)⌊logn⌋1
1.2 二分归并排序的设计思想
设算法Merge Sort(A,p,r)输入A[p…r]输出元素按从小到大排序额数组A
先看以下伪码 二分归并的设计思想
将原问题划分为规模为n/2的两个子问题继续划分将原问题归结为4个子问题继续…当子问题估摸为1时划分结束。从规模1到n/2陆续归并被排好序的两个数组。每归并一次数组规模扩大一倍直到原始数组。
二分归并排序的时间复杂度假设n为2的幂次方二分归并排序最坏时间复杂度为
W(n)2W(n/2)n−1W(n) 2W(n/2) n-1W(n)2W(n/2)n−1 W(1)0W(1) 0W(1)0
可以解出 W(n)nlogn−n1W(n) nlogn - n 1W(n)nlogn−n1 仔细体会着其中的分治策略 1.3 Hanoi塔的递归算法 Hanoi塔的算法设计思想
将原问题归结为规模为n-1的两个子问题继续归结将原问题归结为n-2的四个子问题.继续… 当子问题规模为1时归约过程截止。从规模为1到n-1陆续组合两个子问题的解知道规模为n。
2 小结
将原问题归约为规模较小的子问题子问题与原问题性质完全一样子问题规模足够小时可以直接求解算法可以递归也可以迭代实现算法的分析方法为递推方程
