算法分析精述分享

1. 算法分析的评价体系
   评价算法的三条主要标准是：

   (1) 算法实现所消耗的时间
   (2) 算法实现所消耗的存储空间，其中主要考虑辅助存储空间
   (3) 算法应易于理解、易于编码、易于调试。

2. 算法的时间复杂性
2.1 和算法执行相关的因素

   (1) 问题中数据存储的数据结构
   (2) 算法采用的数学模型
   (3) 算法设计策略
   (4) 问题的规模
   (5) 实现算法的程序设计语言
  (6) 编译算法产生的机器代码的质量
   (7) 计算机执行指令的速度

2.2 算法时间效率的衡量方法

   (1) 事后分析法
       先将算法用程序设计语言实现，然后度量程序的运行时间，这种方法成为事后分析法。你能想到它的缺点???

   (2) 事前分析估算法  
       一个算法的运行工作量的大小，只依赖于问题的规模(通常用整数量n表示)，或者说算法的时间效率是问题规模的函数。
假如随着问题规模n的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作：T(n) = O(f(n)), T(n)简称时间复杂度，
O是数量级的符号。

2.3 时间复杂度估算

    算法的执行时间 =  $[原操作的执行次数 * 原操作的执行时间]， 其中, $表示累加.

    语句的频度指的是该语句重复执行的次数。

   (1) 例子1
    

 for (j = 1; j <= n; j++)
          for(k = 1; k <= n; k++)
              x++;

      分析: 算法段中语句"x++", "k<=n", "x++"的频度是n*n, 语句"j=1", "k=1"的频度是1， 语句"j<=n", "j++"的频度是n。
因此，算法运行的时间是3*n*n + 2*n + 2


  (2) 例子2
     

for (j = 1; j <= n; j++)
          for(k = 1; k <= n; k++)
             for(i = 1; i <= n; i++)
                   s++;

     该算法的时间复杂度为近似n*n*n.

  (3) O    
     在算法的复杂度分析中经常使用一个记号O，读作大O，它是数量级Order的第一个字母。当一个算法的运行时间为n*n+n+1时，
由于n*n+n+1和n*n的数量级相等(该表达式当n足够大时约等于n*n),称它为这个算法的渐进时间复杂度，简称算法的时间复杂度，
记作：T(n) = O(n*n).


  (4) 几种数量级
   
    O(1)            常数级
    O(logn)         对数级
    O(n)            线性级
    O(n的c次方)     多项式级
    O(c的n次方)     指数级
    O(n!)           阶乘级 
  (5) 问题时间复杂度的上界和下界 
  (6) 算法时间复杂度的最好情况和最坏情况

2.4 算法的空间复杂性

   (1) 输入数据所占空间
   (2) 程序本身所占空间
   (3) 辅助存储空间
    

评论

3 楼 andy54321 2010-06-29  

看了，
还有下文吗

2 楼 zhangwe415 2010-06-20  

是算法分析

1 楼 westlifeljz 2010-06-19  

你好想在讲数据结构吗?