分治算法理解 以及在简单算法中的应用

简单的概论

用多次递归的方式进行问题的简化成为一个个简单的问题。然后进行解决问题。用T(n)代表事情的复杂程度,也计算这件事情的最多的时间(相对时间,及抽象的概论时间,没有具体的值但是有具体的,大小范围)!

分层递归的步骤

一,分解

把问题最小化基本的最小文件(最小事情)

二,解决问题(最小事情)

事情足够小,进行简单的解决。

三, 合并

把这些解决方式进行合并计算,最终的出结果。

简单的应用

题目

有一组混乱数组要求你进行从大到小进行排序,用分治法解决。
一共有8个数字。

解决方法

一,先开始进行分解:
把8个数字分解成为两个数组(每一个包含4个数字),然后让这个两个数组重新分成两个数组(每一个数组有4个数字).重复上面的许多次步骤,得到了八个只有一个数字的数组。

二,归并
让简单的两个数组之间进行排序,然后得到了新的4个数组(每一个数组有两个元素)。然后让去重新进行上面步骤,让4个数组进行重新进行并归。得到新的两个数组,然后重行进行上面步骤。最终得到了,一个完全被排序完的数组。
在这里插入图片描述

分析分治算法

基本公式:(其中n为输入数据规模,T(n)为运行时间(相对时间))
O(1) n <= c
T(n) =
aT(a/b) + D(n) + C(n) 其他
当运行一次的时候,其中D(n)为O(1)。

一,分解

让T(n)变成了2T(n/2) + O(n),其中O(n)为化解需要的时间和合并新的数列所需要的时间。
可以得到新的表达式:
O(1 ) n = 1
T(n) =
2T(n/2) + O(n) n > 1
这个表达式也可以改变:
c n = 1
T(n) =
2T(n/2)+ c *n n > 1

二,合并

进行分解完成之后可以得到
T( n) = O(nlogn)(其是定理不用证明)。
上面的shi z都可以用递归数表示
在这里插入图片描

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>