算法分析规则

作者：Flyingis

    算法作为实现计算机程序实现时解决问题的方法，在计算机应用领域发挥着举足轻重的作用。它研究的内容是解决问题的方法，而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。如何去设计一个适合特定应用的优秀算法是众多开发人员所关注的焦点，在算法设计时，需要了解算法设计的规则。<o:p></o:p>

要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。通常我们可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，哪个算法的速度快我们一般就会认为这个算法性能更好。数学方法能将算法分析的更为细致，能在严密的逻辑推理基础上判断算法的优劣，但在完成实际项目过程中，我们很多时候都不能去做这种严密的论证与推断，因为我们不是在完成一道数学难题，也不是数学领域的专家，将大量的时间花费在公式的计算与证明上会导致整个项目进度缓慢、成本过高，因此，在算法设计中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。例如，计算机对n²和n²+2n的响应速度，当n比较大的时候几乎一样没什么区别，我们便可直接认为后者算法的复杂度为n²。在分析算法时，隐藏细节的数学表示法成为大O记法，它可以帮助我们简化算法复杂度的许多细节，提取主要成分，这和遥感图像处理中的主成分分析思想相近。<o:p></o:p>

基于算法复杂度简化表达的思想基础上，我们通常会对算法进行最坏情况分析和平均情况分析。对于一个给定的算法，如果能保证它的最坏情况下的性能依然不错当然很好，但是在某些情况下，程序的最坏情况算法的运行时间和实际情况的运行时间相差很大，在实际应用中我们几乎不会碰到最坏情况下的输入，那么此时进行最坏情况分析显得有些画蛇添足，特别是分析最坏情况算法会花费大量精力的时候。算法的平均情况分析可以帮助我们估计程序的性能，作为算法分析的基本指标之一，但是平均情况和实际情况仍然会有相差很大的时候，这时我们便可以使用随机法来尽量模拟现实中的情况，这样可以得到在严格的概率意义上的预测运行时间。另外，对于一个经典算法，我们没有必要再去对该算法进行改进，研究它的上界和下界，只需要了解该算法的特性，然后在合适的时候使用它。<o:p></o:p>

最后，当一个程序变快和变慢，让计算机反映出来的时间差几乎不会让人产生感觉的时候，我们也没有必要去改进这个算法，例如程序进行1000次循环花费0.001秒，改进后为0.1秒，在实际应用中通常也只需要几千次循环，此时我们就没有必要去花时间来研究这个算法了，只要该算法能正确完成任务即可。<o:p></o:p>