算法合集之《论对题目中算法的选择》

本文介绍了对于一些信息学题目的次好或者差的算法,通过各种举例来说明做题目时并不要一味追求一个完全理想的算法,相对应比较差的算法在实际编程上对于那些好的算法有很大的优势。最后总结出在平常的练习之中,我们需要对一道题目进行多方面的思考,不能抱有知道算法就完事的一种心态,对一道题目,要多考虑新的算法,这样面对形式未见过的题型的时候,就会有更多的思路。

论对题目中算法的选择

【关键词】

非最优算法， 编程复杂度

【摘要】 本文介绍了对于一些信息学题目的次好或者差的算法，通过各种举例来说明做题目时并不要一味追求一个完全理想的算法，相对应比较差的算法在实际编程上对于那些好的算法有很大的优势。最后总结出在平常的练习之中，我们需要对一道题目进行多方面的思考，不能抱有知道算法就完事的一种心态，对一道题目，要多考虑新的算法，这样面对形式未见过的题型的时候，就会有更多的思路。

【正文】

一、引言

计算机竞赛是一项对选手计算机知识、编程能力的综合测试，在平时的训练之中，我们一般都会精益求精，设法想出最好的算法，但是在竞赛的时候，时间和心理状态都是不一样的，如何在竞赛中编出能得分尽量多的程序，是很重要的，所以在平常的练习之中，要有一题多解的概念，把各种算法尝试一下，就会在看似简单的做法中推想出更好的算法。在学习汇编语言的时候，老师这样说，汇编语言编译出的程序是运行速度最快的，为什么，对于一类题目，或者要实现一个目标，人编程用的算法所需要的语句得越多，则机器运行程序速度也就越快，反之人编程用的精力越少，机器运行速度也会越慢。若能找到一个编程难度较低的算法，使程序仍然能在时间限制内运行完成，这样即减轻了人的劳动，又能编写出正确的程序，而且编写的时候错误率也会降低，所以在竞赛中，次好或着差的算法也是可以考虑的。

二、算法的复杂度

我在这里所说的复杂度，包括编程复杂度，时间复杂度，空间复杂度，因为在竞赛几个小时的时间里，编程复杂度就不容忽视，知道算法但是程序没完成，这是最不理想的情况，对源程序的最基本的质量要求是正确性和可靠性，只要保证在这两点的情况下，各种算法都是好算法。但编程复杂度取决于程序的易理解性，易测试性和易修改性，程序不可能都是第一遍就能达到理想的状态，人总有失误的地方，如果有错，不易测试以至难以发现错误，或者知道错误而难以修改，就会浪费不必要的时间。或许，自己对知道的算法还不太熟悉，因为我们不可能对每种算法了解都很透彻，在这种情况下编程序是比较吃亏的，因要花许多时间去了解这种方法。所以在这三个复杂度都考虑的情况下，找到最适宜的算法是必要的。

三、对于一些题目的思路

在我们做题的时候，我们先想出的算法不一定是最好的算法，但不是说明它是不好的算法，所以，在我们想出一种算法的时候，要考虑一下它的可行性，如果可行的话，不如自己先把该算法编一编，可以锻炼自己编那些非标准算法的能力，这样对自己面对新颖题型的时候是会有好处的。

例1．

[问题描述]