作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

算法效率(Algorithm efficency)

    首先提出来算法效率的学习是建立在循环上面的。(The study of algorithm efficency focuses on loops)
   
    1,线形循环(linear loops)
    先看一段代码：
    1  i=1
    2  loop (i <= 1000)
       1  application code
       2  i=i+2
    3 end loop
    显然这个循环内部的语句会执行1000/2次，换句话说我们如果把1000换成n的话，这个循环次数为n/2,我们用
       
         f(n)=n/2
    来表示
 
    2，对数循环(logarithmic loops)
    先看一段代码：
    1  i=1
    2  loop (i <= 1000)
       1  application code
       2  i=i * 2
    3 end loop
    这里我们把i=i+2改为了i=iX2，因此在执行时
   
    multiply  2**iterations<1000
    divide    1000/2**iterations>=1
   
    我们可以得出这个循环的次数是对数级的f(n)=┍log2(n)┑

    3，嵌套循环(nested loops)
    嵌套循环的执行次数为：iterations=outer iterations X inner iterations
    例如:
    1  i=1
    2  loop(i<=10)
       1  j=1
       2  loop(j<=10)
          1  application code
          2  j=j*2
          3  end loop
       4  end loop
    3  i=i+1

显然这个算法的效率就是10*┌log2(n)┐也就是f(n)=┍nlog2(n)┑,当然我们可以的到平方(quadratic)算法，f(n)=n**2;

    4,现在我们用Big-O法来表示这些算法的效率
      可以分为两步：
     a，把每一个效率公式的系数设为1
     b，只留下最高次数的项
    例如：
    11n**2+7n  //我们可以得到效率为：n**2记为O(n**2)

    七种标准效率衡量数据由小到大为O(log2(n)),O(n),O(nlog2(n)),O(n**2),O(n**K),O(c**n),O(n!)

(to be continued)

相关软件：