设计算法
计算机学术语
对算法的学习包括5个方面:设计算法、表示算法、确认算法、分析算法、验证算法。算法设计工作是不可能完全自动化的,应学习了解已经被实践证明有用的一些基本的算法设计方法,这些基本的设计方法不仅适用于计算机科学,而且适用于电气工程、运筹学等领域。设计算法的原则包括:正确性、可读性、健壮性、高效率与低存储量。
定义
算法就是为解决问题而采取的方法与步骤。随着计算机的出现,算法被广泛地应用于计算机的问题求解中,被认为是程序设计的精髓。对算法的学习包括5个方面:设计算法、表示算法、确认算法、分析算法、验证算法。算法设计工作是不可能完全自动化的,应学习了解已经被实践证明有用的一些基本的算法设计方法,这些基本的设计方法不仅适用于计算机科学,而且适用于电气工程、运筹学等领域。
原则
对于一个特定问题的算法在大部分情况下都不是唯一的。也就是说,同一个问题,可以有多种解决问题的算法,而对于特定的问题、特定的约束条件,相对好的算法还是存在的。因此,在特定问题、特定的条件下,选择合适的算法,会对解决问题有很大的帮助;否则前人的智慧我们不能借鉴,凡事就都得自己从头研究了,这就是所谓的要去“发明轮子”。
在设计算法时,通常要考虑以下原则:
正确性
算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需要、能够得到问题的正确答案。
但是算法的“正确”通常在用法上有很大的差别,大体分为以下4个层次:
(1)算法程序没有语法错误;
(2)算法程序能够根据正确的输入的值得到满足要求的输出结果;
(3)算法程序能够根据错误的输出的值满足规格说明的输出结果;
(4)算法程序对于精心设计、极其刁难的测试数据都能满足要求的输出结果。
对于这4层含义,层次(1)要求最低,因为仅仅没有语法错误实在谈不上是好的算法。而层次(4)是最困难的,人们几乎不可能逐一验证所有的输入都得到正确的结果。
因此,算法的正确性在大部分情况下都不可能用程序来证明,而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的,代价非常昂贵。所以一般情况下,人们把层次(3)作为一个算法是否正确的标准。
可读性
设计算法的目的,一方面是为了让计算机执行,但还有一个重要的目的就是为了便于他人的阅读,让人理解和交流,自己将来也可阅读。如果可读性不好,时间长了自己都不知道写了什么,可读性是评判算法(也包括实现它的程序代码)好坏很重要的标志。可读性不好不仅无助于人们理解算法,晦涩难懂的算法往往隐含错误,不易被发现并且难以调试和修改。
健壮性
当输入的数据非法时,算法应当恰当地做出反应或进行相应处理,而不是莫名其妙的输出结果。并且处理出错的方法不应是中断程序的执行,而应是返回一个表示错误或错误性质的值,以便于在更高的抽象层次上进行处理。
高效率与低存储量
通常,算法的效率指的是算法的执行时间;算法的存储量指的是算法执行过程中所需要的最大存储空间,两者的复杂度都与问题的规模有关。算法分析的任务是对设计的每一个具体的算法,利用数学工具,讨论其复杂度,探讨具体算法对问题的适应性。
在满足以上几点以后,还可以考虑对算法进程进一步优化,尽量满足时间效率高和空间存储量低的需求。
步骤
设计算法的一般过程可以归纳为以下几个步骤:
建立数学模型
通过对问题进行详细的分析,抽象出相应的数学模型
确定数据结构与算法
确定使用的数据结构,并在此基础上设计对此数据结构实施各种操作的算法。
选用语言
选用某种语言将算法转化成程序。
调试并运行
调试并运行这些程序。
参考资料
最新修订时间:2022-08-25 12:45
目录
概述
定义
原则
参考资料