1.1 概念

所谓算法，是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。

1. 问题：针对直线上一点作垂直线 模型：绳索和奴隶 算法：勾股定理的方法
2. 问题：三等分线段 模型：直尺和圆规 算法：...略
3. 问题：将若干元素按大小排序 模型：图灵机或ram 算法：bubbleSort()

1.2 要素

1.2.1 输入与输出

可以有多个输入与多个输出。

1.2.2 基本操作

"读取某一元素的内容" 、"修改某一元素的内容"、"比较两个元素的大小"、"逻辑表达式求值"以及"根据逻辑判断确定分支转向"等等，都属于现代电子计算机所支持的基本操作。

1.2.3 确定性和可行性

确定性：算法应描述为若干语义明确的基本操作组成的指令序列。

可行性：指令是可以通过当前计算模型做出的基本操作。

1.2.4 有穷性与正确性

有穷性：随着算法的进行，问题的规模在不断变小 -> 单调性。正确性：保证算法最后结束时候结果的正确性 -> 不变性：算法每一次运行，往正确的结果规模更进一步。

1.2.5 退化与鲁棒性

1.2.6 重用性

1.3 算法效率

1.3.1 可计算性

1.3.2 难解性

1.3.3 计算效率

为了高效率解决计算问题，为此，首先需要确立一种尺度，用以从时间和空间等方面度量算法的计算成

本，进而依此尺度对不同算法进行比较和评判。当然，更重要的是研究和归纳算法设计与实现过程中的

一般性规律与技巧，以编写出效率更高、能够处理更大规模数据的程序。

1.3.4 数据结构

1.4 复杂度度量

1.4.1 时间复杂度

问题实例的规模往往是决定计算成本的主要因素。

随着问题规模的扩大，执行时间的变化趋势称为时间复杂度。

1.4.2 渐进复杂度

• 最坏、最好与平均情况
• 大Ο记号（上界）
• 大Ω记号（下界）
• 大Θ记号（确界：对于任何规模的输入，运行时间都与复杂度同阶）

1.4.3 空间复杂度

1.5 复杂度分析

1.5.1 常数Ο(1)

1.5.2 对数Ο(logn)

1.5.3 线性Ο(n)

1.5.4 多项式Ο(n2)

1.5.5 指数Ο(2n)

1.5.6 输入规模

用以描述输入所需的空间规模（可以根据算法本身操作的对象来找）。

比如求2n，输入规模应该看成2进制的位数。

1.6 递归

1.6.1 递归要素

• 递归基
• 递归方程
• 递归模式

1. 多递归基

在判断递归基时有if-else。算法举例：

1. 数组倒置算法

2. 多向递归

在递归的时候有if-else判断。算法举例：

1. 幂函数递归算法

1.6.2 递归形式

1.6.2.1 线性递归

算法可能朝着更深一层进行自我调用，且每一递归实例对自身的调用至多一次。于是，每一层次上至多

只有一个实例，且它们构成一个线性的次序关系。此类递归模式因而称作"线性递归"（linear recursion），它也是递归的最基本形式。比如：数组求和的递归算法。

减而治之

线性递归的模式， 往往对应于所谓减而治之（decrease-and-conquer）的算法策略：递归每深入一层，待求解问题的规模都缩减一个常数，直至最终蜕化为平凡的小（简单）问题。

1.6.2.2 二分递归

将问题分解为若干规模更小的子问题，再通过递归机制分别求解。这种分解持续进行，直到子问题规模

缩减至平凡情况。既然每一递归实例都可能做多次递归，故称作"多路递归"（multi-way recursion）。通常都是将原问题一分为二，故称作"二分递归"（binary recursion）。需强调的是，无论是分解为两个还是更大常数个子问题，对算法总体的渐进复杂度并无实质影响。

二分递归效率问题

并非所有问题都适宜于采用分治策略。实际上除了递归，此类算法的计算消耗主要来

自两个方面。首先是子问题划分，即把原问题分解为形式相同、规模更小的多个子问题，比如二分

sum()算法将待求和数组分为前、后两段。其次是子解答合并，即由递归所得子问题的解，得到原问题的整体解，比如由子数组之和累加得到整个数组之和。为使分治策略真正有效，不仅必须保证以上两方

面的计算都能高效地实现， 还必须保证子问题之间相互独立——各子问题可独立求解，而无需借助其它子问题的原始数据或中间结果。否则，或者子问题之间必须传递数据，或者子问题之间需要相互调用，

无论如何都会导致时间和空间复杂度的无谓增加，如斐波那契数列的二分递归算法。

分而治之

分而治之（divide-and-conquer）策略。

1.6.2.3 多分支递归

1.6.3 递归算法复杂度计算

1.6.3.1 递归跟踪

算法的每一递归实例都表示为一个方框，其中注明了该实例调用的参数2. 若实例M调用实例N，则在M与N对应的方框之间添加一条有向联线

1.6.3.2 递推方程（recurrence equation）

与递归跟踪分析相反，该方法无需绘出具体的调用过程，而是通过对递归模式的数学归纳，导出复杂度

定界函数的递推方程（组）及其边界条件，从而将复杂度的分析， 转化为递归方程（组）的求解。比如 sum(A, n-1)的递归方程组为：

1. T(n) = T(n - 1) + Ο(1) = T(n - 1) + c12. T(0) = Ο(1) = c2

联立解得：T(n) = c1n + c2 = Ο(n)

1.6.4 递归优化

1.6.4.1 尾递归

1.6.4.2 制表（tabulation）或记忆（memoization）策略

1.6.4.3 动态规划

1.7 抽象数据类型

1.7.1 抽象数据类型（abstract data type, ADT）

数据集合及其对应的操作，接口。

1.7.2 数据结构（data structure, ds）

数据结构是对抽象数据类型的实现，接口实现。