算法复杂度Tnppt课件.ppt

文档介绍：该【算法复杂度Tnppt课件 】是由【bb21547】上传分享，文档一共【79】页，该文档可以免费在线阅读，需要了解更多关于【算法复杂度Tnppt课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
分治法的初衷
任何一个问题的求解时间都与其规模有关。
例子:
n个元素排序:
当n=1,不需计算;
当n=2,只作一次即可;
当n=3,两次即可…
显然,随着n的增加,问题也越难处理。
2
分治法
分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
如果问题可分割成k个子问题,且这些子问题都可解,利用这些子问题可解出原问题的解,此分治法是可行的。
由分治法产生的子问题往往是原问题的较少模式,为递归提供了方便。
3
递归
递归:一直接/间接调用自身的算法成为递归算法。
intFactorial(intn)
if(n==0)
return1
returnn*Factorial(n-1)
递归第一式给出函数的初值,非递归定义。每个递归须有非递归初始值。
第二式是用较小自变量的函数值表示较大自变量
阶乘函数
4
递归
前面提到的
算法前面已讨论过
Fibonacci数列
上述函数也可用非递归方式定义:
但并非一切函数都可用非递归方式定义。
5
双递归函数
一个函数与它的一个变量是由函数自身定义。
m=0,A(n,0)=n+2
m=1,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2
m=2,
Ackerman函数
6
双递归函数
部分书上减少Ackerman函数的变量,如:
m=3,,其中2的层数n
m=4,A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数。
7
整数划分问题
将正整数n表示成一系列正整数之和:
n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。
正整数n的这种表示称为正整数n的划分。
求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分:
6;
5+1;
4+2,4+1+1;
3+3,3+2+1,3+1+1+1;
2+2+2,2+2+1+1,2+1+1+1+1;
1+1+1+1+1+1。
8
整数划分问题
前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。
在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。
(2)q(n,m)=q(n,n),mn;
最大加数n1实际上不能大于n。因此,q(1,m)=1。
(1)q(n,1)=1,n1;
当最大加数n1不大于1时,任何正整数n只有一种划分形式,
即
9
整数划分问题
(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;
正整数n的最大加数n1不大于m的划分由n1=m的划分和
n1≤m-1的划分组成。
(3)q(n,n)=1+q(n,n-1);
正整数n的划分由n1=n的划分和n1≤n-1的划分组成。
前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。
在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。
10
整数划分问题
前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解。
在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系:
正整数n的划分数p(n)=q(n,n)