算法的Magic

一、算法的定义

    是指解决问题的一种方法或者一个过程，更严格来说，算法是由若干条指令组成的”有穷序列”。具有输入、输出、确定性和有限性。

二、算法设计的基本方法

    列举法、归纳法、递推、递归、减半递推技术、回溯法等。

三、算法复杂度

1)算法复杂度定义

    算法复杂性的衡量标准是运行该算法所需要消耗的计算机资源的多少，其中，资源包括时间和空间两个部分，因此算法复杂性由时间复杂性和空间复杂性两个部分构成。

2）衡量算法的复杂性

    我们一般使用最好情况、最坏情况和平均情况衡量算法的复杂性，其中最坏情况是运行实例的最长时间，最好情况是运行实例的最短时间，而平均情况则是所有可能情况与其对应出现的概率的乘积之和。平均情况的估计，在一定的程度上体现了最大熵的原理。

3）算法的复杂性符号

    为描述算法的复杂性，引入了五种衡量算法复杂性的渐进意义下的符号。分别为O, o, Omega, omega, Theta. 其分别表示为上确界，上紧确界，下确界，下紧确界，渐进确界；

    在进行上紧确界，下紧确界的证明时，如果使用定义不能得到，那么可以使用比值极限的方法，上紧确界中原函数比上确界函数的极限为0，而下紧确界原函数比下紧确界函数极限为无穷大;