Loading... ## 数据结构的基本概念 ### 数据结构的三要素 - 逻辑结构 - 线性结构 - 非线性结构 (集合，树，图) - 存储结构 - 顺序存储 - 非顺序存储 (链式，索引，散列) > 存储数据时，不仅要存储数据的值，还要存储数据元素之间的关系。 - 数据的运算 根据逻辑结构来定义，根据存储结构来实现。 数据结构通过三要素来确定，所以对于两种不同的数据结构，逻辑结构和存储结构可能完全一致。比如二叉树和二叉排序树。 ### 数据类型 数据类型是一个**值的集合**和定义在此集合上的**一组操作**的总称。 - 值的集合：也就是数据类型可取得的值的范围。比如 `bool` 类型的取值范围为 `true, false` 两种。 - 一组操作：指数据类型支持的操作。比如 `int` 类型可以支持 `+, -, *, /, ...` 多种操作。 数据类型可以细分为两种： 1. 原子类型，其值不可再分的数据类型。比如 C 中的 `int, bool, float` 之类的类型。 2. 结构类型，其值可以再分解为若干成分的数据类型。比如 C 中的结构体。 ### 抽象数据类型 抽象数据类型 (Abstract Data Type, **ADT**) 是抽象数据组织及与之相关的操作。 ADT 用数学化的语言定义数据的逻辑结构和运算，与具体的实现无关。 > 定义了一个 ADT ，就是定义了数据的逻辑结构和运算，也就是定义了一个数据结构。 ## 算法和算法评价 程序 = 数据结构 + 算法。 算法 (Algorithm) 是对**特定问题求解步骤的一种描述**，它是指令的有限序列，其中每条指令表示一个或多个操作。 > 算法就是求解问题的步骤。 ### 算法的特性 - 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可以在有穷时间内完成。 > 算法必须是有穷的，而程序不是。比如操作系统就不是有穷的。 - 确定性。算法中每条指令必须有确切的含义，对于**相同的输入**只能得出**相同的输出**。 - 可行性。算法中描述的操作都可以通过已经实现的**基本运算执行有限次**来实现。 - 输入。一个算法有零个或多个输入，取自于某个特定对象的集合。 - 输出。一个算法也有一个或多个输出，这些输出与输入有着某种特定关系的量。 **一个“好”的算法的特质：** - 正确性。 - 可读性。 - 健壮性。 - 高效率与低存储需求。 ### 算法的开销 #### 时间复杂度 算法的时间复杂度为**事前预估**算法的**时间开销 $T(n)$** 与**问题规模 $n$** 之间的关系。 > $O(n)$ 表示 $n \rightarrow \infty$ 时，该算法的复杂度和 $n$ 是同阶的。 $$ O(1) < O(log_2n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) $$ > "常对幂指阶" #### 空间复杂度 空间复杂度只需分析**除输入和程序之外的额外空间**。 当算法运行所需的内存空间和问题规模 $n$ 无关时，算法空间复杂度 $S(n) = O(1)$ ，此时称算法可以**原地工作**。 最后修改：2024 年 04 月 26 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏