0.算法设计与分析__绪论

算法及其重要特性

算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。

算法的五大特性： ⑴ 输入：一个算法有零个或多个输入。 ⑵ 输出：一个算法有一个或多个输出。 ⑶ 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

问题的求解过程： 分析问题→设计算法→编写程序→整理结果 算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。

例子： 欧几里德算法——辗转相除法求两个自然数 m 和 n 的最大公约数

算法设计的一般过程 1．理解问题 2．预测所有可能的输入 3. 在精确解和近似解间做选择 4. 确定适当的数据结构 5．算法设计技术 6．描述算法 7．跟踪算法 8．分析算法的效率 9．根据算法编写代码

算法分析 算法分析（Algorithm Analysis）：对算法所需要的两种计算机资源——时间和空间进行估算 时间复杂性（Time Complexity） 空间复杂性（Space Complexity）

算法分析的目的： 设计算法——设计出复杂性尽可能低的算法 选择算法——在多种算法中选择其中复杂性最低者

时间复杂性分析的关键： 问题规模：输入量的多少； 基本语句：执行次数与整个算法的执行时间 成正比的语句

渐进符号

1. 大O符号 定义1.1 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))，或称算法在O(f(n)中。
2. 大Ω符号 定义1.2 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))
3. Θ符号 定义1.3 若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))

最好、最坏和平均情况 结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。 最好情况：出现概率较大时分析 最差情况：实时系统 平均情况：已知输入数据是如何分布的， 通常假设等概率分布

非递归算法的分析

1. 决定用哪个（或哪些）参数作为算法问题规模的度量
2. 找出算法中的基本语句
3. 检查基本语句的执行次数是否只依赖于问题规模
4. 建立基本语句执行次数的求和表达式
5. 用渐进符号表示这个求和表达式

关键：建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。