- 1、本文档共62页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第二章欧拉图及哈密顿图
* 第三节 * 通用性:算法适用于一类输入。 问题是要求回答的提问通常有几个参数它们的值是特定的,取自定义域。 问题的描述:是对参数进行描述,指出其解是满足什么性质的命题。 实例 :给问题的全体参数都指定了确定的值便得到一个问题的实例。 A是问题P的算法,若算法A对问题P的每个实例都给出正确答案。 问题P算法可解,若存在一个算法解答问题P。 算法分析 是指通过分析得到算法所需的时间和空间的估计量。 算法的复杂度是指执行算法所需的时间和空间的量。 定义1 令f和g为从整数集合或实数集合到实数集合的函数,如果存在常数c和k,使得只要x?k,就有?f(x)? ?c?g(x)?则称f(x)是O(g(x))记为f(x)=O(g(x)) 读作f(x)是O(g(x)) 定理1: 令f(x)=an xn +an-1 xn-1 +…+a1 x+a0其中a0 、a1 、 …、 an-1 、 an为实数,则f(x)=O(xn) 定理2 设f1 (x)=O(g1 (x))、 f2 (x)=O(g2 (x)) ,则f1 (x) + f2 (x) =O(max(g1 (x)、 g2 (x)))。 定理3 设f1 (x)=O(g1 (x))、 f2 (x)=O(g2 (x)),则f1 (x) *f2 (x) =O(g1 (x)* g2 (x))。 例1 对于正整数n,给出n!和logn!的大O估计. 解:n!=1*2*3*…*n?nn,故n!=O(nn), 又logn! ?lognn =nlogn,所以logn! =O(nlogn). 例2 给出f(n)=3n*logn!+(n2+3)*logn的大O估计,其中n是正整数。 解:logn!=O(nlogn),故3n*logn!=O(n2logn) 所以f(n)= O(n2logn). 例3 给出f(x)=(x+1)log(x2+1)+3x2的大O估计。 解:当x1时,x2+1?2x2; 当x2时,Log(x2+1)?log(2x2) ?3logx, 故Log(x2+1)=O(logx),所以(x+1)Log(x2+1)=O(xlogx) 又x1时,xlogx ?x2,所以f(x)=O(x2). 复杂性 术语 复杂性 术语 O(1) O(logn) O(n) O(nlogn) 常数复杂性 对数复杂性 线性复杂性 nlogn复杂性 O(nk) O(bn),b?1 O(n!) 多项式复杂性 指数复杂性 阶乘复杂性 易处理的,能用多项式最坏情况复杂性的算法解决的问题,否则称为不易处理的. P问题:易处理的问题. NP问题:至今没有找到多项式算法,又不能证明它不存在多项式算法的一类问题. NPC问题:其中任何一个问题能用一个多项式时间最坏情况算法解答的一类问题。 例4 冒泡排序 它把一个列表排列成升序;相继地比较相邻的元素,若它们顺序不对,则交换它们。试分析冒泡排序 的最坏时间复杂度。O(n2) 1 2 3 4 3 2 2 2 2 3 3 3 4 4 4 1 1 1 1 4 5 5 5 5 2 2 3 1 1 3 4 4 5 5 2 1 2 3 3 4 4 5 5 1 2 3 4 5 冒泡排序解答 第五节 最短路路问题 1.加权图:边上有数的图称为加权图;该数称为边的权。 2.最短路问题:如何求两个结点之间的最短路. 3. Dijkstra算法: 这是荷兰计算机科学教授Edsger W.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项. 迪克斯曲拉算法是求出一个连通加权简单图中从结点a到结点z的最短路.边{i,j}的权?(i,j)0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度. 4. Dijkstra算法流程 Procedure Dijkstra(G:所有权为正的加权连通简单图) {G带有顶点a=v0,v1,…,vn=z和权w(vi,vj),若{vi,vj}不是G中的边,则w(vi,vj)=?) For i:=1 to n L(vi):= ? L(a):=0 S:=? {初始化标记,a的标记为0,其余结点标记为?,S是空集} While z?S begin u:=不属于S的L(u)最小的一个顶点 S:=S?{u} For 所有不属于S的顶点v If L(u)+w(u,v)L(v) then L(v):=L(u
文档评论(0)