没有合适的资源?快使用搜索试试~ 我知道了~
计算机算法分析与设计论文-背包问题的算法设计策略对比与分析.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 17 浏览量
2024-03-27
09:09:40
上传
评论 1
收藏 51KB DOCX 举报
温馨提示
试读
33页
计算机算法分析与设计论文-背包问题的算法设计策略对比与分析.docx
资源推荐
资源详情
资源评论
实用文档
.
算 法 设 计 与 分 析 课 程 考 查 论 文 .
.
.
.
背包问题的算法设计策略对比与分析.
.
.
.
.
.
0-1 背包问题的算法设计策略对比与分析.
0 引言.
对于计算机科学来说,算法(Algorithm)的概念是至关重要的。算法是一
系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获
得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将
不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任
务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。.
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或
者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解
决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描
述。.
一个算法应该具有以下五个重要的特征:.
有穷性:一个算法必须保证执行有限步之后结束;.
确切性:算法的每一步骤必须有确切的定义; .
输入:一个算法有 0 个或多个输入,以刻画运算对象的初始情况,所谓 0 个
输入是指算法本身定除了初始条件; .
输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有
输出的算法是毫无意义的; .
可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即
可完成。.
实用文档
计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》,
可见算法在计算机科学界与计算机应用界的地位。.
1 算法复杂性分析的方法介绍.
算法的复杂性是算法效率的度量,是评价算法优劣的重要依据。一个算法的
复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越
多,我们就说该算法的复杂性越高;反之,所需的资源越低,则该算法的复杂性
越低。 .
计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复
杂性有时间复杂性和空间复杂性之分。 .
不言而喻,对于任意给定的问题,设计出复杂性尽可能地的算法是我们在设
计算法是追求的一个重要目标;另一方面,当给定的问题已有多种算法时,选择
其中复杂性最低者,是我们在选用算法适应遵循的一个重要准则。因此,算法的
复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 .
关于算法的复杂性,有两个问题要弄清楚:用怎样的一个量来表达一个算法
的复杂性;对于给定的一个算法,怎样具体计算它的复杂性。.
让我们从比较两对具体算法的效率开始。.
1.1 比较两对算法的效率.
考虑问题 1:已知不重复且已经按从小到大排好的 m 个整数的数组 A[1..m]
(为简单起见。还设 m=2 k,k 是一个确定的非负整数)。对于给定的整数 c,要
求寻找一个下标 i,使得 A[i]=c;若找不到,则返回一个 0。.
问题 1 的一个简单的算法是:从头到尾扫描数组 A。照此,或者扫到 A 的
第 i 个分量,经检测满足 A[i]=c;或者扫到 A 的最后一个分量,经检测仍不满足
A[i]=c。我们用一个函数 Search 来表达这个算法:.
Function Search (c:integer):integer;.
Var J:integer; .
Begin.
J:=1; {初始化}.
{在还没有到达 A 的最后一个分量且等于 c 的分量还没有找到时,.
查找下一个分量并且进行检测} .
实用文档
While (A[i]<c)and(j<m) do .
j:=j+1; .
If A[j]=c then search:=j {在数组 A 中找到等于 c 的分量,且此分量的下标
为 j} .
else Search:=0; {在数组中找不到等于 c 的分量}.
End;.
容易看出,在最坏的情况下,这个算法要检测 A 的所有 m 个分量才能判断
在 A 中找不到等于 c 的分量。.
解决问题 1 的另一个算法利用到已知条件中 A 已排好序的性质。它首先拿
A 的中间分量 A[m/2]与 c 比较,如果 A[m/2]=c 则解已找到。如果 A[m/2]>c,则
c 只可能在 A[1],A[2],..,A[m/2-1]之中,因而下一步只要在 A[1], A[2], .. ,A[m/2-1]
中继续查找;如果 A[m/2]<c,则 c 只可能在 A[m/2+1],A[m/2+2],..,A[m]之中,因
而下一步只要在 A[m/2+1],A[m/2+2],..,A[m]中继续查找。不管哪一种情形,都把
下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与 c 比
较,重复上述步骤。照此重复下去,总有一个时候,或者找到一个 i 使得
A[i]=c,或者子数组为空(即子数组下界大于上界)。前一种情况找到了等于 c
的分量,后一种情况则找不到。.
这个新算法因为有反复把供查找的数组分成两半,然后在其中一半继续查找
的特征,我们称为二分查找算法。它可以用函数 B_Search 来表达:.
Function B_Search ( c: integer):integer;.
Var.
L,U,I:integer;{U 和 L 分别是要查找的数组的下标的上界和下界}.
Found:boolean;.
Begin.
L:=1; U:=m; {初始化数组下标的上下界}.
Found:=false; {当前要查找的范围是 A[L]..A[U]。}.
{当等于 c 的分量还没有找到且 U>=L 时,继续查找}.
While (not Found) and (U>=L) do.
Begin.
I:=(U+L) div 2;{找数组的中间分量}.
实用文档
If c=A[I] then Found:=Ture.
else if c>A[I] then L:=I+1 .
else U:=I-1;.
End;.
If Found then B_Search:=1.
else B_Search:=0;.
End;.
容易理解,在最坏的情况下最多只要测 A 中的 k+1(k=logm,这里的 log 以 2
为底,下同)个分量,就判断 c 是否在 A 中。.
算法 Search 和 B_Search 解决的是同一个问题,但在最坏的情况下(所给定
的 c 不在 A 中),两个算法所需要检测的分量个数却大不相同,前者要 m=2 k 个,
后者只要 k+1 个。可见算法 B_Search 比算法 Search 高效得多。.
.
.
.
.
.
以上例子说明:解同一个问题,算法不同,则计算的工作量也不同,所需的
计算时间随之不同,即复杂性不同。.
上图是运行这两种算法的时间曲线。该图表明,当 m 适当大(m>m0)时,
算法 B_Search 比算法 Search 省时,而且当 m 更大时,节省的时间急剧增加。.
不过,应该指出:用实例的运行时间来度量算法的时间复杂性并不合适,因
为这个实例时间与运行该算法的实际计算机性能有关。换句话说,这个实例时间
不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们
引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率,而不想去
比较运行该算法的计算机的性能。因而,不应该取算法运行的实例时间作为算法
复杂性的尺度。我们希望,尽量单纯地反映作为算法精髓的计算方法本身的效率,
而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。.
实用文档
1.2 复杂性的计量.
算法的复杂性是算法运行所需要的计算机资源的量,需要的时间资源的量称
作时间复杂性,需要的空间(即存储器)资源的量称作空间复杂性。这个量应该
集中反映算法中所采用的方法的效率,而从运行该算法的实际计算机中抽象出来。
换句话说,这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本
身的函数。如果分别用 N、I 和 A 来表示算法要解问题的规模、算法的输入和算
法本身,用 C 表示算法的复杂性,那么应该有:.
C =F(N,I,A).
其中 F(N,I,A)是 N,I,A 的一个确定的三元函数。如果把时间复杂性和空间复
杂性分开,并分别用 T 和 S 来表示,那么应该有:.
T =T(N,I,A) (2.1).
和 S =S(N,I,A) (2.2).
通常,我们让 A 隐含在复杂性函数名当中,因而将(2.1)和(2.2)分别简
写为.
T =T(N,I).
和 S =S(N,I).
由于时间复杂性和空间复杂性概念类同,计算方法相似,且空间复杂性分析
相对地简单些,所以下文将主要地讨论时间复杂性。.
下面以 T(N,I)为例,将复杂性函数具体化。.
根据 T(N,I)的概念,它应该是算法在一台抽象的计算机上运行所需的时间。
设此抽象的计算机所提供的元运算有 k 种,他们分别记为 O1,O2 ,..,Ok;再设这
些元运算每执行一次所需要的时间分别为 t1,t2,..,tk 。对于给定的算法 A,设经
过统计,用到元运算 Oi 的次数为 ei,i=1,2,..,k ,很明显,对于每一个 i,
1<=i<=k,ei 是 N 和 I 的函数,即 ei=ei(N,I)。那么有:.
(2.3).
其中 ti,i=1,2,..,k,是与 N,I 无关的常数。.
剩余32页未读,继续阅读
资源评论
omygodvv
- 粉丝: 504
- 资源: 2078
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功