教案 程序设计—数据结构 第一章绪论 2、事前分析估算法 和算法执行时间相关的因素： 1）算法选用的策略 2)问题的规模 3)编写程序的语言 4)编译程序产生的机器代码的质量 5)计算机执行指令的速度 3、时间复杂度 1)定义 一个特定算法的“运行工作量”的大小，只依赖于问题的规模(（通常用整数量表示)， 或者说，它是问题规模的函数。 假如，随着问题规模的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T(n)=O(f(n)) 称T()为算法的（渐近）时间复杂度 2)例子 例1-4-1如下为NXN矩阵相乘的算法，乘法运算是“矩阵相乘问题”的基本操作。整个 算法的执行时间与该基本操作（乘法）重复执行的次数m成正比，记作T)=O() for (i=1:i<=n:++i) for(j=1;j<=n;++j){ ci]]=0: for(k=1;k<=n;++k) c[i][]+=a[i][k]*b[k][j]; } 例1-4-2 void select sort(int a[],int n){ ∥将a中整数序列重新排列成自小至大 ∥有序的整数序列。 for(i=0;i<n-1;++i){ j=正 for(k=i+l:k<n:++k) if(ak<ajl）j=k if(j!=i)a]+→a可 }f∥select sort void bubble sort(int a.int n) ∥将a中整数序列重新排列成自小至大 ∥有序的整数序列。 for i=n-1,change=TRUE;i>1 &change;--i){ change=FALSE: for(j-0;j<i;++j) if (a[j]>a[j+1]){ aj]+→aj+l] change=TRUE; } 文档编号 完成时间 完成人张昱 修改时间2003-9-3 第5页程序设计——数据结构 第一章 绪论 第 5 页 文档编号 完 成 人 张 昱 完成时间 修改时间 2003-9-3 2、事前分析估算法 和算法执行时间相关的因素： 1）算法选用的策略 2）问题的规模 3）编写程序的语言 4）编译程序产生的机器代码的质量 5）计算机执行指令的速度 3、时间复杂度 1) 定义 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量 n 表示）， 或者说，它是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n)的增长率相同，则可记作： T (n) = O(f(n)) 称 T (n) 为算法的(渐近)时间复杂度 2) 例子 例 1-4-1 如下为 N×N 矩阵相乘的算法，乘法运算是“矩阵相乘问题”的基本操作。整个 算法的执行时间与该基本操作(乘法)重复执行的次数 n 3 成正比，记作 T(n) = O(n 3 ) 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]; } 例 1-4-2 void select_sort(int a[], int n) { // 将 a 中整数序列重新排列成自小至大 // 有序的整数序列。 for ( i = 0; i< n-1; ++i ) { j = i; for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j = k; if ( j != i ) a[j] ←→ a[i] } // select_sort void bubble_sort(int a[], int n) { // 将 a 中整数序列重新排列成自小至大 // 有序的整数序列。 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; }