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