算法复杂度

算法复杂度

算法由控制结构（if else, for, while）和原操作构成，算法时间取决于两者的综合效果。
通常从算法中选取一种对所研究的问题业说是基本操作的原操作，以该基本操作重复执行的次数为算法的时间量度。

人们通常采用“大O”表示法：说某个算法的时间代价(或者空间代价)为O(f(n))，则表示如果存在正的常数c和n0，当问题的规模n≥n0后，该算法的时间(或空间)代价T(n)≤c·f(n)。这时也称该算法的时间(或空间)代价的增长率为f(n)。这种说法意味着：当n充分大时，该算法的复杂性不大于f(n)的一个常数倍。

１．加法规则

      T(n) = T1(n)+ T2(n)  = O(f1(n)) + O(f2(n))

               = O(max(f1(n), f2(n)))

2. 乘法规则

    T(n) = T1(n)×T2(n) = O(f1(n)) ×O(f2(n))= O(f1(n)×f2(n))        

采用 “大O表示法”简化了时间和空间代价的度量，其基本思想是主要关注复杂性的量级：最坏情况下的代价(对同样规模的问题所花费的最大代价)、最好情况下的代价和平均情况下的代价等。

关心当n充分大时，函数T(n)=？

  

  常数，对数，线性，二次，指数（增长率）。

下面考虑二个n阶矩阵乘法的时间复杂性：（乘法是这个二个n阶矩阵乘法问题的基本操作）

Cn´n =An´n ´Bn´n 程序如下：

for(i=0;  i   i++)

    for(j=0;  j   j++)

        {  c[i][j]=0;

             for(k=0;  k   k++)

                 c[i][j] = c[i][j]+a[i][k]*b[k][j];

        }

时间复杂性为：

 

上图是几种函数增长速度比较曲线。