正确答案
作为实现计算机程序实现时解决问题的方法,算法研究的内容是解决问题的方法,而不是计算机程序的本身。一个优秀的算法可以运行在比较慢的计算机上,但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要,因此,在计算机程序设计中,算法设计往往处于核心地位。
要想充分理解算法并有效地应用于实际问题,关键是对算法的分析。通常可以利用实验对比分析、数学方法来分析算法。实验对比分析很简单,两个算法相互比较,它们都能解决同一问题,在相同环境下,一般就会认为哪个算法的速度快这个算法性能更好。在算法设计中,通常采用能近似表达性能的方法来展示某个算法的性能指标。例如,计算机对n2和n2+2n的响应速度,当n比较大的时,没什么区别,便可直接认为后者算法的复杂度为n2。
基于算法复杂度简化表达的思想基础上,通常会对算法进行最坏情况分析和平均情况分析。对于一个给定的算法,如果能保证它的最坏情况下的性能依然很好,但是在某些情况下,程序的最坏情况算法的运行时间和实际情况的运行时间相差很大,在实际应用中几乎不会碰到最坏情况下的输入,那么此时进行最坏情况分析显得有些画蛇添足,特别是分析最坏情况算法会花费大量精力的时候。算法的平均情况分析可以帮助估计程序的性能,作为算法分析的基本指标之一,但是平均情况和实际情况仍然会有相差很大的时候,这时便可以使用随机法来尽量模拟现实中的情况,这样可以得到在严格的概率意义上的预测运行时间。另外,对于一个经典算法,没有必要再去对该算法进行改进,研究它的上界和下界,只需要了解该算法的特性,然后在合适的时候使用它。
试题解析