数据结构 绪论教程.ppt

[例] 冒泡排序算法 数据结构---第一章 绪论 * void bubble_sort(int a[ ], int n ) { //将a中n个数据序列重新排列成自小至大有序的整数序列 for (i=n-1, change=TRUE; i=1 change; --i) { change=FALSE; for ( j=0; ji; ++j) if ( a[j]a[j+1] ) { a[j] a[j+1]; change=TRUE; } } }//bubble_sort 数据结构---第一章 绪论 * 一些约定 1）预定义常量和类型： //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status作为函数的类型，其值是函数结果状态代码 typedef int Status; 2）数据元素类型约定为ElemType，使用时按需定义 数据结构---第一章 绪论 * 1.3.3 算法分析 ——算法效率的度量 一个具体问题的数据对象往往可以采用多种存储方式的一种，一个问题的解决又常常有多种可用的算法。 1）时间复杂度 算法的消耗时间：算法中每条语句执行时间之和。 时间复杂度：算法中各语句的频度之和T(n)。 频度—语句的执行次数； n—问题的规模，一般为数据的输入量 渐近时间复杂度：当问题的规模n趋于无穷大时， T(n)的数量级(阶)。记为T(n)=O( f(n) )。 O的严格含义— 存在正的常数c和n0，使得当n? n0时， 0? T(n) ? c*f(n) 实际中，将渐近时间复杂度简称为时间复杂度，用以描述算法的时间特性。 和算法消耗时间相关的因素： 算法选用的策略 问题的规模 编写程序的语言 编译程序产生的机器代码的质量 计算机执行指令的速度 数据结构---第一章 绪论 * 时间复杂度的求法 计算T(n) 从T(n)中推断f(n) 影响算法时间复杂度的因素 问题的规模 输入实例的初态 常见的时间复杂度 O(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n) 好 差 数据结构---第一章 绪论 * [例1] 交换i和j的内容 (1) temp=i; (2) i=j; (3) j=temp; 解：T(n)=3 记作T(n)= O(1) 数据结构---第一章 绪论 * [例2] n?n矩阵相乘的算法语句 for ( i=1; i=n; i++ ) n+1 for (j=1; j=n; j++) n(n+1) { c[i, j]=0; n2 for (k=1; k=n; k++) n2(n+1) c[i, j]=c[i, j]+a[i, k]*b[k, j]; n3 } 解：语句频度 T(n)=2 n3 +3 n2 +2n+1 当n?n0=1时，有T(n)?8n3 ，即c=8，由此取f(n)= n3 则T(n)=O(n3) 算法中存在循环时，通常由嵌套层数最深的循环语句的最内层语句决定 数据结构---第一章 绪论 * [例3] 在数组A[1..n]查找给定值K (1) i