大学计算机重要课程第一章绪论.ppt

算法的评价——衡量算法优劣的标准 正确性(correctness): 满足具体问题的需求 可读性(readability)： 易读、易理解 健壮性(robustness): 当输入数据非法时，算法能够做出反应或进行处理 效率与低存储量: 执行时间短、存储空间小 算法效率的度量 算法效率的度量 时间代价：算法在计算机上运行时消耗的时间来度量。有两种方法： 事后统计的方法：利用计算机内部计时功能，进行计时统计。 缺陷——必须先运行程序；统计的时间依赖于计算机的软硬件环境，容易掩盖算法本身的优劣。 事前分析估算的方法 假设给定的是一台通用计算机，满足： 执行一条基本语句或一个基本运算需花一个单位时间 基本语句指：赋值语句、输入语句、输出语句 基本运算指：算术运算、一次比较（字符比较、数值比较） 做法：从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 例8-1 两个N×N矩阵A和B相乘的算法。 for (i=0;in;i++) for (j=0;jn;j++) {c[i][j]=0; for (k=0;kn;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 基本操作 时间复杂度：基本操作重复执行的次数是问题规模n的某个函数，记作 T(n)=O(f(n)) “O” 标记的形式定义： 若f(n)是正整数n的一个函数，则xn＝O(f(n))表示存 在一个正的常数M，使得当n?n0时都满足|xn|?M|f(n)|； (换句话就是说，这当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。) 例8-2 N×N矩阵相乘的算法的时间复杂度： 基本操作执行的次数：n×n×n=n3 ∴T(n)=O(n3) 语句的频度：是指该语句重复执行的次数。与该语句包含的基本操作执行的次数相同。 例8 分析语句{++x; s=0;}的频度。 解：将“++x”看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)；如果将“s=0”也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。 例9 分析语句for (i=1; i=n; ++i) {++x; s+=x;} 解：语句频度为：2n，其时间复杂度为：T(n)=O(n)。即时间复杂度为线性阶。 例10 分析语句for (i=1; i=n; ++i) 　　　　 for (j=1; j=n; ++j) {++x; s+=x;} 解：语句频度为：2n2，其时间复杂度为：O(n2)。即时间复杂度为平方阶。 定理：若A(n)=amnm +am-1nm-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)。(证明略) 例11 for (i=2; i=n; ++i) for (j=2; j=i-1; ++j) {++x; a[i,j]=x;} 解：语句的频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2)/2 ∴时间复杂度为T(n)=O(n2) 即此算法的时间复杂度为平方阶。 练习：x=n; y=0; while (x = (y + 1)(y + 1)){ y++;} 以下六种计算算法