算法的效率

效率是速度和空间消耗的度量。集中考虑程序的速度，也称运行时间或执行时间，用复杂度的阶(O)这一标准来衡量。空间的消耗或需求也可以用大O表示，而且它总是小于或等于时间需求。

 

以下是我的学习笔记：

 

1.求值与霍纳法则，即为秦九韶公式。

 

2.测定运行时间的最可靠方法是计数对运行时间有贡献的基本操作的执行次数。运行时间与这个计数成正比。

 

3.在分析程序的运行时间时，重要的是把程序看成算法，即独立于实现它的程序设计语言的一系列步骤。

 

4.一般地，算法是由多个基本操作组成的。有时我们计数所有的基本操作，而有时计数一个主导操作。

 

5.需要在算法的运行时间与它所操作的输入的规模之间建立关系。

 

6.需要观察不同的输入规模下的运行状况。特别需要作为输入规模的函数的比较次数。

 

7.在分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。

 

8.函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么，说f(n)的增长渐近快于g(n)。

 

9.大O：给定两个函数f(n)和g(n)，f(n)=O(g(n))当且仅当存在一个常数c使得c*g(n)的增长渐近快于f(n)。

 

10.常数阶O(1)：表示运行时间与输入规模无关。实例：访问数组中第i项的操作的运行时间

 

11.线性阶O(n)：实例：在有n个值的数组中寻求最大(或最小)值的算法。

 

12.二次阶：实例：简单的多项式求值方案、选择排序算法。

 

13.对数阶(关于二叉搜索算法)、nlogn阶(某些排序算法)、三次阶。

 

14.指数阶：O(k^n)，其中k是某个与输入规模n无关的常数，一般在解决特殊问题中探索“所有可能选择”(应用穷举)的算法中最常遇到。实例：给定n个整数，我们希望知道是否存在这些整数的一个子集，使得这个子集中的整数之和等于另一个给定整数K。

 

15.如果x比y增长得慢，那么x超前于y，用“<”表示，有如下顺序：1<logn<n^(1/2)<nlogn<n^(3/2)<n^2<n^3<k^n。

 

16.阶函数中的变量：对于出现在算法输入规模中的每一个变量，算法的运行时间的阶函数中至多有一项包含该变量。

 

17.通常，运行时间从最好情况运行时间到平均情况运行时间，再到最坏情况运行时间不断升级。

 

18.通常，除非特别指定，运行时间就是最坏情况运行时间。

 

19.通常，使用“时间复杂度”指运行时间需求，并使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，他们通常指时间复杂度。另外，如果他们没有特指平均情况或最坏情况，一般指的是最坏情况。

 

20.一个算法的空间需求总是小于或等于它的时间需求。