算法分析初步

好的算法可以使程序更加出色的解决实际问题，因此关于好的算法的标准是必要的，算法的分析主要是针对
算法的效率而言的。好的算法要节省空间及时间资源。


空间代价：算法在运行过程中消耗的存储空间。
时间代价：算法运行所需要的时间。


测试算法效率的方法有很多种，每种测试方法的侧重点也各不相同。算法分析技术中最常用的一种方法
称为：算法的事前估计（算法被调用前进行）。


事前估计分为对算法空间复杂度的度量与对算法时间复杂度的度量。
空间复杂度是指当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占用的存储空间以
某种单位由1增加到s(n),则称此算法的空间复杂度为s(n) 。
时间复杂度是指当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所耗费的时间以某种
单位由1增加到t(n),则称此算法的空间复杂度为t(n) 。


对于这个空间复杂度和时间复杂度的估计通常的得到的只是算法在空间代价和时间代价方面的近似值，并
非准确值！这是因为准确值的获得将使估计过程十分繁琐，也没有必要。
在对算法进行估计时直接估计算法中时间（空间）复杂度最大的部分就可以了，这称为时间（空间）复杂
度的渐进表示法。
利用渐进表示法得到的算法复杂度通常用字母O表示，称为大O表示法。大O表示法得到的是算法复杂度的数
量级信息，这个数量级信息是程序在最坏情况下的时间（空间）代价。


使用大O表示法时有加法规则与乘法规则：
*大O表示法的加法规则是指当两个并列的程序段的时间代价不同时，那么将这两个程序段连在一起后整个
程序段的时间代价为大的那个。
*大O表示法的乘法规则是指当两个嵌套的程序段的时间代价不同时，那么整个程序段的时间代价为两个之
积。
使用大O表示法估计程序复杂度只需考虑程序关键操作的步数，而无需考虑非关键操作对算法复杂度造成的
影响。（关键操作大多存在于循环与递归中。对于单个循环而言，在循环内的简单语句即为关键操作。对
于多个并列的循环而言，先计算各个循环的算法复杂度，最后再利用大O表示法的加法规则计算整个并列循
环的算法复杂度）