《数据结构的C++伪码实现》（《DATA STRUCTURES A Pseudocode Approach with C++》）读书笔记(三) (转)
算法效率(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)
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/10752019/viewspace-962689/ ，如需转载，请注明出处，否则将追究法律责任。
