《数据结构的C++伪码实现》(《DATA STRUCTURES A Pseudocode Approach with C++》)读书笔记(三)

类别:软件工程 点击:0 评论:0 推荐:

算法效率(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)

本文地址:http://com.8s8s.com/it/it37580.htm