15-算法设计的4个目标

0.5.1　算法设计的4个目标

一个好的算法应该实现以下4个目标。

1．算法的正确性

算法的 正确性 是指算法至少应该包括对于输入、输出和处理的无歧义性描述，能正确反映需求，且能够得到问题的正确答案。

通常算法的正确性应包括以下4个层次。

（1）算法对应的程序没有语法错误。

（2）对于几组输入数据均能得到满足规格要求的输出。

（3）对于精心选择的、典型的、苛刻的几组输入数据均能得到满足规格要求的输出。

（4）对于一切合法的输入都能得到满足规格要求的输出。

对于这4层算法正确性的含义，达到第4层的正确性是极困难的，所有不同输入数据的数量大得惊人，逐一验证的方法是不现实的。一般情况下，我们把前3个层次作为衡量一个算法是否正确的标准。

2．可读性

可读性 好有助于人们对算法的理解，晦涩难懂的程序往往隐含不易被发现的错误，难以调试和修改。

3．鲁棒性

鲁棒性 是指当输入数据不合法时，算法也应该能做出反应或进行处理，而不会产生异常或莫名其妙的输出结果。例如，求一元二次方程ax²+bx+c=0(a≠0)的根的算法，需要考虑多种情况，先判断b²−4ac的值的正负，如果其值为正数，则该方程有两个不同的实根；如果其值为负数，则表明该方程无实根；如果其值为0，则表明该方程只有一个实根。如果a=0，则该方程又变成了一元一次方程。此时，若b=0，还要处理除数为0的情况。如果输入的a、b、c不是数值型，还要提示用户输入错误。

4．高效率和低存储量

效率指的是算法的执行时间。对于同一个问题，如果有多个算法能够解决，执行时间越短的算法效率越高，执行时间越长的算法效率越低。存储量指算法在执行过程中需要的最大存储空间。效率和存储量都与问题的规模有关，如求100个人的平均分与求1000个人的平均分所花的执行时间和存储空间显然有一定的差别。设计算法时应尽量选择高效率和低存储量的算法。