1.算法的定义及特性

   算法(Algorithm)是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性！！！

（1）有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。

（2）确定性。对于每种情况下所执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。

（3）可行性。算法中的所有操作都可以通过以及实现的基本操作运算执行有限次来实现。

（4）输入。一个算法有零个或多个输入。当用函数描述算法是，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。

（5）输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法是，输出多用返回值或引用类型的形参表示。

2.评价算法优劣的基本标准

（1）正确性。在合理的数据输入下，能够在有限的运行时间内得到正确的结果。

（2）可读性。一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。

（3）健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。

（4）高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用储存容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

3.算法的时间复杂度

    算法效率分析的目的是看算法实际是否可行，并在同一问题存在多个算法时，可进行时间和空间性能上的比较，以便从中挑选出较优算法。

    衡量算法效率的方法主要有两类:事后统计法和事前分析估算法。事后统计法需要先将算法实现，然后测算其时间和空间开销。这种方法的缺陷很显然，一是必须把算法转换成可执行的程序，二是时空开销的测算结果依赖于计算机的软硬件等环境因素，这容易掩盖算法本身的优劣。所以我们通常采用事前分析估算法，通过计算算法的渐近复杂度来衡量算法的效率。

    一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数 f(n)，算法的时间量度记作

                                                T（n）= O（f（n））

    它表示随问题规模n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度（Time Complexity）

4.算法的空间复杂度

    关于算法的储存空间需求，类似与算法的时间复杂度，我们采用渐进空间复杂度（Space Complexity）作为算法所需储存空间的量度，简称空间复杂度，它也是空间规模n的函数，记作：

                                                   S（n）= O（f（n））

    一般情况下，一个程序在机器执行时，除了需要寄存本身所用的指令，常数，变量和输入数据外，还需要一些对数据进行操作的辅助储存空间。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需分析该算法在实现中所需要的辅助空间就可以了。若算法执行所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法原地工作，辅助空间为O(1)。