算法性能分析

度量算法效率的方法：

Ø事后统计：将算法实现，测算其时间和空间开销。

缺点：⑴编写程序实现算法将花费较多的时间和精力；

            ⑵ 所得实验结果依赖于计算机的软硬件等环境因素。

Ø事前分析：对算法所消耗资源的一种估算方法。

选取对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。

多数情况下，人们所说的基本操作的重复次数都是指最深层循环内的语句的重复执行次数，即语句的频度。

#define n 100

void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n])

{  int i,j,k;

/*1*/   for (i=1;i<=n; i++)       

 /*2*/        for (j=1;j<=n; j++)

/*3*/  {  C[i][j]=0;            

 /*4*/             for (k=1;k<=n, k++) 

 /*5*/                C[i][j]=C[i][j]+A[i][k]*B[k][j];

     }

   }

T(n)=O(n3)

判定算法性能的一个基本考虑是处理一定“规模” 的输入时该算法所需要执行的“基本操作” 数。----渐进算法分析

大O表示法：

定义：如果存在正常数c和n0,使得当N≥n0,时，T(N)≤cf(N), 则记为T(N)=O(f(N))。