算法复习

[TOC]

第一章 算法引论

1.1 表达算法的抽象机制

通俗：算法是指解决问题的方法和过程

严格：算法是满足下述性质的指令序列->

1. 输入：有零个或者多个外部量作为算法的输入。
2. 输出：算法产生至少一个量作为输出
3. 确定性：组成算法的每条指令是清晰的、无歧义的
4. 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限

程序和算法不同：程序是算法用某种程序设计语言的具体实验。程序可以不满足算法的性质->有限性可以把操作系统的各种任务看成一些单独的问题，每一个问题的由操作系统中的一个子程序通过特定的算法实现。该子程序得到输出结果后便终止

高级程序设计语言在数据、运算和控制三方面的表达中引入许多使之十分接近算法语言的概念和工具，具有抽象表达算法的能力。高级程序设计语言的主要好处是：

1. 高级语言更接近算法语言，易学、易掌握
2. 提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好、可维护性强、可靠性高
3. 高级语言不依赖于机器语言，因而可植性好、重用率高。
4. 把琐碎的事物交给编译程序，所以自动化程度更高、开发时间短

对一个数学问题-> 选用数据模型->初始状态、结果状态以及两个状态间的隐含关系->运算步骤（算法）

自顶向下求精原则：先考虑算法顶层的运算步骤|数据模型级上的运算步骤|(宏观步骤)->底层运算步骤：1、数据模型的具体表示2、定义在数据模型上的运算的具体实现|（底层运算步骤）

抽象数据类型：

1. 算法设计和数据结构设计隔开，允许数据结构自由选择，从中比较
2. 数据模型和该模型上的运算同一在抽象数据类型中，反映它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，灵活的满足用户需求。
3. 由于顶层设计和底层设计是局部化的，便于查找和纠正错误，具有很好的可维护性。
4. 算法自然呈现模块化，抽象数据类型的表示和实现可以封装，便于移植和重用
5. 为自顶向下逐步求精和模块化提供有效途径和工具
6. 算法结构清晰，层次分明，便于算法准确性的证明和复杂性的分析

1.2 算法复杂性分析

自变量：N、I和A表示算法要解决的问题的规模、算法的输入和算法本身，用C表示复杂性 C = F(N, I, A)