数据结构与STL绪论分析.ppt

《数据结构与STL》 * 欧几里得算法描述举例 伪代码描述： 程序设计语言描述： 1. input m,n 2. r=m%n; 3. while (r!=0) 3.1 m=n; 3.2 n=r; 3.3 r=m%n; 4. output n; int EUCLID (int m, int n) { int r = m % n; while (r != 0){ m = n; n = r; r = m % n; } return n; } 《数据结构与STL》 * 欧几里得算法描述举例 采用面向对象的方法描述： class NaturalNumber{ public: unsigned long int EUCLID(NaturalNumber n); //欧几里德算法求解最大公约数 //……其它外部接口 private: unsigned long int num; //存储真正的自然数 }; //返回欧几里德算法求解最大公约数 unsigned long int NaturalNumber :: EUCLID(NaturalNumber n) { unsigned long int m = (num n.num) ? num : n.num; //较大的自然数赋值给m unsigned long int n = (num n.num) ? num : n.num; //较小的自然数赋值给n unsigned long int r = m % n; while (r != 0) {m = n; n = r; r = m % n;} return n; } 算法效率的衡量方法和准则 算法执行时间的相关因素 算法选用的策略 问题的规模 编写程序的语言 编译程序产生的机器代码的质量 计算机执行指令的速度 事后统计法 必须执行程序 其他因素掩盖算法本质 事前分析估算法 《数据结构与STL》 * 算法好坏的评价: 算法的时间复杂度 算法的空间复杂度 算法的可读性 ...... 算法的执行时间: 与哪些因素相关？ 问题规模通常是指算法处理的数据量的大小，记作 n。 运行算法所需要的时间 T 可看作问题规模n的函数， 记作T(n)。 算法分析 计算工具 对算法执行时间的度量 算法本身 …… 问题的规模 《数据结构与STL》 * 语句的频度（frequency count） 即：语句执行的次数 假定每条语句执行一次所需的时间是单位时间，则每条语句执行的时间正比于该语句执行的次数 算法运行时间≈算法中所有语句的频度之和。 ① for (i=0; in; i++) n+1 ② for (j=0; jn; j++) n(n+1) ③ k++; n2 语句的频度 算法的总用时：T(n)=2n2+2n+1 算法时间复杂度的估算 算法的工作量：所有语句的频度之和； (但过于具体将非常繁琐，而且不能反映时间耗费的本质)； 算法 = 控制结构+原操作 原操作法：基本操作----原操作 设f(n)为原操作对n的函数， 执行时间= 原操作(i)的执行次数*原操作(i)的执行时间 《数据结构与STL》 * 算法的渐进时间复杂度 当表达式结果为常数 T(n)与n2是同阶的 T(n)与n2是同数量级的 记作T(n)=O(n2) 称为算法的时间复杂度 时间复杂度也可以利用算法中的基本语句计算 基本语句：执行次数与算法的执行次数成正比的语句。 《数据结构与STL》 * 分析算法的时间复杂度 j += i; i = j - i; j = j - i; for (i=0;i100;i++) for (j=0;ji;j++) sum += j; for (i=0;in;i++) for (j=0;j=i;j++) sum += j; O(1) O(1) O(n2) 《数据结构与STL》 * y=0; while ((y+1)*(y+1)=n) y++; ∵(T(n)+1)2≤ n ∴T(n)=O(n1/2) i=0,j=0; while (i+jn){ if (ij) j++; else i++; } O(n) 《数据结构与STL》 * 特殊情况下的算法时间复杂度 最好的执行次数 最坏的执行次数 平均时间复杂度 在数组a[n]中查找值为k的元素，若找到返回其位置i（0≤i＜n），否则返回-1。 int i=n-1; while(i=0 a[i]