数据结构与算法（ Java 描述）第1章数据结构和算法

数据结构与算法（Java 描述）

标签：数据结构、算法、Java
时间：2022年7月13日 17点53分
连接：
来源：数据结构与算法（Java 描述）邓俊辉著

第一章算法及其复杂度 13

§1.1 计算机与算法 14

1.1.1 过指定垂足的直角边 14

1.1.2 三等分线段 15

1.1.3 排序 16

起泡排序算法

最大元素必然就位

只关注前面的n-1 个元素

1.1.4 算法的定义 19

算法还必须具备以下要素：
- 输入：待处理的信息，即对具体问题的描述。比如，对于上述三个例子来说，输入分别是“任意给定的直线以及其上的一点”、“任意给定的一条线段”以及“由 n 个可比较元素组成的序列”。
- 输出：经过处理之后得到的信息，即问题的答案。比如，对于上述三个例子来说，输出分别是我们所要得到的“垂直线”、“三等分点”以及“完全有序的序列”。
- 确定性：任一算法都可以描述为由若干种基本操作组成的序列。在垂直线算法中，“取等长绳索”、“联结绳索”、“将绳结固定于一点”、“沿特定方向拉直绳索”等操作都属于基本操作。在三等分线段算法中，基本操作就是欧氏作图法所允许的所有尺规操作。而在起泡排序算法中，基本操作就是图灵机所允许的各种操作：“读取某一元素的内容”、“比较两个元素的大小”以及“修改某一元素的内容”等等。
- 可行性：在相应的计算模型中，每一基本操作都可以实现，且能够在常数时间内完成。
- 有穷性：对于任何输入，按照算法，经过有穷次基本操作都可以得到正确的输出。

§1.2 算法性能的分析与评价 20

1.2.1 三个层次 20

1.2.2 时间复杂度及其度量 20

1.2.3 空间复杂度 22

§1.3 算法复杂度及其分析 23

1.3.1 O(1)((取非极端元素 23

1.3.2 O(logn)((进制转换 23

1.3.3 O(n)((数组求和 24

1.3.4 O(n2)((起泡排序 25

1.3.5 O(2r)((幂函数 25

§1.4 计算模型 26

1.4.1 可解性 26

1.4.2 有效可解 27

1.4.3 下界 27

§1.5 递归 27

1.5.1 线性递归 28

1.5.2 递归算法的复杂度分析 32

1.5.3 二分递归 33

1.5.4 多分支递归 36