文档介绍：1 、算法的时间性能分析(1 )算法耗费的时间和语句频度一个算法所耗费的时间= 算法中每条语句的执行时间之和每条语句的执行时间= 语句的执行次数( 即频度(Frequency Count)) × 语句执行一次所需时间算法转换为程序后, 每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时间耗费,则设每条语句执行一次所需的时间均是单位时间,一个算法的时间耗费就是该算法中所有语句的频度之和。求两个 n 阶方阵的乘积 C=A × B, 其算法如下: # define n 100 //n 可根据需要定义, 这里假定为 100 void MatrixMultiply(int A[a] , int B [n][n] , int C[n][n]) { // 右边列为各语句的频度 int i ,j ,k; (1) for(i=0; i< n;j++) n+1 (2) for (j=0;j < n;j++) { n(n+1) (3) C[i][j]=0; n 2 (4) for (k=0; k< n; k++) n 2 (n+1) (5) C[i][j]=C[i][j]+A[i][k]*B[k][j]; n 3 }} 该算法中所有语句的频度之和( 即算法的时间耗费) 为: T(n)=2n 3 +3n 2 +2n+1 () 分析: 语句(1) 的循环控制变量 i 要增加到 n ,测试到 i=n 成立才会终止。故它的频度是 n+1 。但是它的循环体却只能执行 n 次。语句(2) 作为语句(1) 循环体内的语句应该执行 n 次,但语句(2) 本身要执行 n+1 次,所以语句(2) 的频度是 n(n+1) 。同理可得语句(3) , (4) 和(5) 的频度分别是 n 2,n 2 (n+1) 和n 3。算法 MatrixMultiply 的时间耗费 T(n) 是矩阵阶数 n 的函数。(2 )问题规模和算法的时间复杂度算法求解问题的输入量称为问题的规模(Size), 一般用一个整数表示。矩阵乘积问题的规模是矩阵的阶数。一个图论问题的规模则是图中的顶点数或边数。一个算法的时间复杂度(plexity, 也称时间复杂性)T(n) 是该算法的时间耗费,是该算法所求解问题规模 n 的函数。当问题的规模 n 趋向无穷大时, 时间复杂度 T(n) 的数量级(阶) 称为算法的渐进时间复杂度。算法 MatrixMultidy 的时间复杂度 T(n) 如() 式所示,当 n 趋向无穷大时,显然有这表明,当 n 充分大时, T(n) 和n 3 之比是一个不等于零的常数。即 T(n) 和n 3 是同阶的,或者说 T(n) 和n 3 的数量级相同。记作 T(n)=O(n 3) 是算法 MatrixMultiply 的渐近时间复杂度。(3 )渐进时间复杂度评价算法时间性能主要用算法时间复杂度的数量级( 即算法的渐近时间复杂度) 评价一个算法的时间性能。算法 MatrixMultiply 的时间复杂度一般为 T(n)=O(n 3), f(n)=n 3 是该算法中语句(5) 的频度。下面再举例说明如何求算法的时间复杂度。交换 i和j 的内容。 Temp=i; i=j; j=temp; 以上三条单个语句的频度均为 1,