1.4 算法和算法分析【荐】.ppt

数据结构 第1章 绪论 1.1什么是数据结构 1.2基本概念和术语 1.3抽象数据类型的表示与实现 1.4算法和算法分析 1.4 算法和算法分析 1.4.1算法 一、算法：对特定问题求解步骤的一种描述，它是指 令的有限序列，其中每一条指令表示一个或多个操作。 二、算法的5个重要特性： 有穷性：一个算法必须总是（对任何合法的输入值） 在执行有穷步之后结束，且每一步都可在有穷时间 内完成。 确定性：算法中每一条指令必须有确切的含义，不 存在二义性。且对于相同的输入只能得出相同的输 出。 1.4 算法和算法分析 可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 1.4 算法和算法分析 1.4.2算法设计的要求 正确性：算法应满足具体问题的需求。 a）程序不含语法错误；b）程序对于一般输入数据的正确性；c）程序对于苛刻、刁难输入数据的正确性；d）程序对于一切合法输入数据的正确性。 可读性：算法应该好读。以有利于人对程序的理解。 1.4 算法和算法分析 健壮性：算法应具有容错处理。当输入非 法数据时，算法应对其作出反应，而不是 产生莫名其妙的输出结果。 效率：算法执行时间。 存储量需求：算法执行过程中所需要的最 大存储空间。 一般，这两者与问题的规模有关。 1.4 算法和算法分析 1.4.3算法效率的度量 一、算法执行时间的度量方法： 1）事后统计的方法：收集此算法的执行时间和实际占用空间的统计资料。 缺陷： a）必须先运行依据算法编制的程序； b）依赖于计算机的硬件、软件等环境因素。 1.4 算法和算法分析 2）事前分析估算的方法：求出该算法的一个时 间界限函数。 算法运行所消耗的时间取决于： a）依据的算法选用何种策略； b）问题的规模； c）书写程序的语言； d）编译程序所产生的机器代码的质量； e）机器执行指令的速度。 1.4 算法和算法分析 二、算法的时间复杂度 原操作：基本操作。 算法的时间度量：原操作重复执行的次数。 算法的渐近时间复杂度：原操作重复执行的次数是问题规模n的某个函数f(n) T(n)=O(f(n)) 频度：原操作重复执行的次数。 1.4 算法和算法分析 常见的时间复杂度有： O(1) 常量阶 O(n) 线性阶 O(n2) 平方阶 O(n3) 立方阶 O(log n) 对数阶 O(2n) 指数阶 六种常用计算算法时间的多项式的关系为： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 1.4 算法和算法分析 三、求算法时间复杂度举例 例1{++x; s=0;} 将++x看成是基本操作，则语句频度为１，即时间 复杂度为Ｏ(1)，即常量阶。 例2 for(i=1; i=n; ++i) {++x; s+=x;} 将++x看成是基本操作，语句频度为n，其时间 复杂度为为O(n)，即时间复杂度为线性阶。 1.4 算法和算法分析 例3 for(i=1; i=n; ++i) 　　 for(j=1; j=n; ++j) {++x; s+=x;} 将++x看成是基本操作，语句频度为 n2，其时间复杂度为O(n2)，即时间复 杂度为平方阶。 1.4 算法和算法分析 在难以精确计算基本操作执行次数的情况 下，只需求出它关于n的增长率或阶即可。 例4 for(i=2;i=n;++i) for(j=2;j=i-1;++j) {++x; a[i][j]=x;} 将++x看成是基本操作，语句频度为(n-1)(n- 1)/2，其时间复杂度可近似为O(n2)，即它关于n 的增长率或阶。 1.4 算法和算法分析 当基本操作执行次数随问题的输入数据集变化时， 计算平均时间复杂度或最坏情况下的上界。 例5 起泡排序算法 void bubble_sort(int a[], int n) {for (i=n-1,change=TRUE; i=1 change; --i ) { change = FALSE; for(j = 0; j i; j++) if (a[j]a[j+1]) {a[j]?a[j+1];change=TRUE;}