1.绪论：数据结构 + 算法的特性 + 时间/空间复杂度

一、绪论

1.1. 数据结构

1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

2. 数据元素：数据的基本单位，一个数据元素可由若干数据项组成。

3. 数据项：数据的不可分割的最小单位。

4. 数据对象：性质相同的数据元素的集合，是数据的一个子集。

5. 数据结构：指互相之间存在着一种或多种特定关系的数据元素的集合，包括逻辑结构，存储结构和对数据的运算。（数据元素都不是孤立存在的）。

6. 抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作，只取决于它的一组逻辑特性，用一个三元组表示（D, S, P）。

7. 数据类型：是程序设计语言中的一个概念，它是一个值的集合和操作的集合。

8. 逻辑结构 ：是指数据之间关系的描述，与数据的存储结构无关。分为线性结构和非线性结构，通常分为四类结构：

   1. 集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
      2. 线性结构：结构中的数据元素之间存在一对一的关系。
      3. 树型结构：结构中的数据元素之间存在一对多的关系。
      4. 图状结构（网状结构）：结构中的数据元素之间存在多对多的关系。

9. 存储结构 ：是指数据结构在计算机中的表示，又称为数据的物理结构。它包括数据元素的表示和关系的表示，通常由四种基本的存储方法实现：

   1. 顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素，存储位置反映数据元素间的逻辑关系，存储密度大。有些操作（如插入、删除）效率较差。
   2. 链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针，指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），且不能折半查找。
   3. 索引存储方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。
   4. 散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

1.2. 算法

1.2.1. 算法的基本概念

1. 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。
2. 算法的特性 ：有穷性、确定性、可行性、输入、输出。
3. 算法的设计目标 ：正确性，可读性，健壮性，高效率与低存储量需求。

算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。

1.2.2. 算法的时间复杂度

1. 如何计算：

   1. 找到一个基本操作（最深层循环)
      2. 分析该基本操作的执行次数x与问题规模n的关系 x = f ( n ) x=f(n) x=f(n)
      3. x的数量级 O ( x ) O(x) O(x)就是算法时间复杂度 T ( n ) T(n) T(n)： O ( x ) = T ( n ) O(x)=T(n) O(x)=T(n)

2. 常用技巧：

   1. 加法规则： O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) O(f(n))+O(g(n))=O(max(f(n), g(n))) O(f(n))+O(g(n))=O(max(f(n),g(n)))

      2. 乘法规则： O ( f ( n ) ) × O ( g ( n ) ) = O ( f ( n ) × g ( n ) ) O(f(n))×O(g(n))=O(f(n)×g(n)) O(f(n))×O(g(n))=O(f(n)×g(n))

         3. “常对幂指阶”
            O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3
            ) < O ( 2 n ) < O ( n ! ) < O ( n n )
            O(1)2)3)n)n)
            O(1)

3. 三种复杂度：

   1. 最坏时间复杂度：考虑输入数据“最坏”的情况。
      2. 平均时间复杂度：考虑所有输入数据都等概率出现的情况。
      3. 最好时间复杂度：考虑输入数据“最好”的情况。

算法的性能问题只有在 n 很大时才会暴露出来

1.2.3. 算法的空间复杂度

1. 普通程序：

   1. 找到所占空间大小与问题规模相关的变量
      2. 分析所占空间 x 与问题规模 n 的关系 x = f ( n ) x=f(n) x=f(n)
      3. x 的数量级 O ( x ) O(x) O(x) 就是算法空间复杂度 S ( n ) S(n) S(n)

2. 递归程序：

   1. 找到递归调用的深度x与问题规模n的关系 x = f ( n ) x=f(n) x=f(n)
      2. x的数量级 O ( x ) O(x) O(x) 就是算法空间复杂度 S ( n ) S(n) S(n)