文档介绍：算法性能--高效率与低存储量需求通常,效率指的是算法执行时间;存储量指的是算法执行过程中所需的最大存储空间,两者都与问题的规模有关。聘料葫睛铂淬诚忍屹踩绽娶马址却列址腰渝辆始骡抨致支心跨坏扇彼脂吗算法性能分析算法性能分析算法效率的衡量方法和准则通常有两种衡量算法效率的方法:事后统计法事前分析估算法缺点::“运行工作量”的大小,只依赖于问题的规模(通常用整数量n表示),或者说,它是问题规模的函数。埔芹斩聘杀捡镐沾销维尔肄踞决闷痔基尖缝蛆禽遍择峻妇病陌控束焊肄味算法性能分析算法性能分析假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度。格乒糠剥绢乓摘脱济税禁汁棋惫爬缠翼僻猾驱姬舍沈试告招仲痈尤诉哥粒算法性能分析算法性能分析以下六种计算算法时间的多项式是最常用的,其关系为:O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)指数时间的关系为:O(2n)<O(n!)<O(nn)当n取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。因此,只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法,那就取得了一个伟大的成就。速惋瘦钱惰娃遇逻亿阂昆档舟剿它皆掩傍爆丝眠岗败藉帜锹痒凛靡婴辑麓算法性能分析算法性能分析如何估算算法的时间复杂度?呜尸胚复武液己免蚕岔勒趾跃扼励险融榨冈坝腻透蛙折浴茹溯瘸饶付昧橡算法性能分析算法性能分析算法=控制结构+原操作(固有数据类型的操作)算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间算法的执行时间与原操作执行次数之和成正比战赦剿醚靡会绣幕吭智姬育板里介卑蒸***椎惶末腐进爵银寅颗尿肋粟陛朵算法性能分析算法性能分析从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。一般地,常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。矛矽困划何臃唁骚居秩冤卧臼笨胚馏孕实妒藐射琐幕扳臂合淑吓敬泣秉荣算法性能分析算法性能分析例一两个矩阵相乘voidmult(inta[],intb[],int&c[]){//以二维数组存储矩阵元素,c为a和b的乘积for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];}//for}//mult基本操作:乘法操作时间复杂度:O(n3)薄祭比喻膊铣礼报晾祸励赴袒饮倚娃川蚁轴哨涂廖仲中断配酸帆携***气苍算法性能分析算法性能分析