基本概念

---

算法（Algorithm） 是指解题方案的准确而完整的描述。在计算机科学领域中算法几乎无处不在，在各种计算机系统的实现中，算法的设计往往处于核心的位置。

特征

---

特性	描述
有穷性	有穷性是指必须能在执行有限个步骤之后结束，并且每一步都可以在有限的时间内完成
确切性	每一个步骤必须具有确切的定义，是无二义性的
输入性	一个算法有0个或多个输入（所谓0个输入是指算法本身就嵌入了输入）
输出性	一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果
可行性	任何操作都是可以被分解为基本的可执行的步骤

标准

---

标准	描述
正确性	正确性是指在合理的数据输入下，能在有限的时间内得出正确的结果
可读性	算法主要是为了人的阅读与交流，其次才是让计算机执行，因此算法应该易于人的理解
健壮性	算法应当具备检查错误和对错误进行适当处理的能
效率	指算法执行时所需计算机资源的多少，包括运行时间和存储空间两方面的要求 （时间复杂度、空间复杂度）

描述方式

---

自然语言描述

自然语言法是指用文字叙述的形式描述集合的方法。自然语言来描述算法的优点是更便于对算法的理解和阅读，缺点是不够严谨易产生歧义。当使用自然语言描述比较复杂的结构算法时，就不够直观清晰了。

流程图

使用特定图形符号加上文字说明表示具体流程和算法思路的一种框图，通俗地讲就是 “流程”+“图”。除了说明程序的流程顺序外，着重于说明程序的逻辑性。

伪代码描述

伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而且比自然语言或算法框图更接近程序设计语言。

高级程序设计语言描述法

使用特定的可以直接在计算机上执行的程序描述算法。优点是不用转换直接可以编译执行，缺点是需要对特定的程序设计语言比较理解。（所谓“程序”是指对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说 数据结构+算法=程序）

算法设计方法主要有分治策略、动态规划、贪心算法、回溯法、搜索、概率算法等。

模拟法与枚举法

---

模拟法

基本思想

现实生活中有些问题难以找到公式或规律来求解，只能按照一定的步骤不停的模拟下去， 最后才能得到答案。 这样的问题用计算机求解十分合适，只要能让计算机模拟人在解决此问题时的行为即可。这种求解问题的思想，称为模拟。

枚举法

基本思想

逐一列举问题所涉及的所有情形，并根据问题提出的条件检验排查出是问题的解。（也称为列举法、穷举法，是暴力策略的具体体现）

特点

（1）枚举算法的思路简单，正确性容易证明，方便程序编写和调试

（2）当问题的规模变大的时候，运算量过大，执行速度越慢，解题效率不高

解题步骤

（1）确定枚举对象；

（2）确定枚举范围和判断条件；

（3）逐一筛选出问题的解。

常用语法：循环+判断语句。

优化

由于枚举法对要所有可能的情况进行筛选，不重复不遗漏地进行检验，通过牺牲时间来换取答案的全面性。为此优化的主要方向是：

（1）减少状态总数，从而减少计算量；

（2）将原问题化为更小的问题，根据问题的性质进行剪枝；

【经典例题】水仙花数、百钱买百鸡等