| date | author | title | url | tags | series | categories | toc | draft | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
2022-11-02 08:17:14 +0800 |
Rustle Karl |
算法 |
posts/cpp/algorithm/README |
|
|
|
true |
false |
数据是描述客观事物的符号，是能输入到计算机中并被计算机程序处理的符号集合。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
或称数据项。是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包含 3 个方面的内容：逻辑结构、储存结构（物理结构）和对数据的运算。
数据结构的逻辑结构是对数据元素之间的关系的描述，与数据的存储结构无关，同一种逻辑结构可以有多种不同的存储结构。
线性结构是数据元素之间存在一对一的线性关系。
有 4 个基本特征：
- 有且仅有一个被称为“第一个”的数据元素；
- 有且仅有一个被称为“最后一个”的数据元素；
- 除第一个数据元素外，其余数据元素有且仅有一个被称为“前驱”的数据元素；
- 除最后一个数据元素外，其余数据元素有且仅有一个被称为“后继”的数据元素；
线性结构包括：线性表、栈、队列、串。
非线性结构是数据元素之间存在一对多的非线性关系。
非线性结构包括：树、图。
指数据的逻辑结构在计算机中的表示（映像）。包括数据元素的表示和关系的表示。
当数据元素是由若干个数据项组成时，数据元素的表示称为数据域。
数据元素之间的关系有 2 种表示方法：顺序映像和非顺序映像。对应的储存结构称为顺序储存结构和非顺序储存结构。
顺序映像是借助数据元素在存储器种的相对位置来表示数据元素之间的逻辑关系。
非顺序映像是借助指针来表示数据元素之间的逻辑关系。
实际上，在数据结构种有以下 4 种常用的储存方法：
把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元中，结点之间的逻辑关系由储存单元的邻接关系来体现。
由此得到的储存结构称为顺序储存结构。
把逻辑上相邻的数据元素存储在物理位置上不一定相邻的存储单元中，结点之间的逻辑关系由指针来体现。
由此得到的储存结构称为链式储存结构。
索引存储方法在存储结点信息时除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引项的一般形式是<关键字，地址>。关键字标识唯一一个结点，地址作为指向结点的指针。
散列存储方法的基本思想是根据结点的关键字通过散列函数直接计算出该结点的存储地址。这种存储方法本质上是顺序存储方法的扩展。
算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列。
算法具有以下 5 个特性：
- 有穷性：一个算法必须保证执行有限步之后结束。
- 确定性：算法中的每一步都有确切的含义，不会出现二义性。
- 可行性：算法中的所有操作都必须通过已经实现的基本操作进行运算，并在有限次内实现。
- 输入：算法具有零个或多个输入。
- 输出：算法至少有一个或多个输出。
算法设计目标包括正确性、可读性、健壮性和算法效率4个方面，其中算法效率通过算法的时间复杂度和空间复杂度来描述。
- 正确性：能够正确地执行预先规定的功能和性能要求。
- 可读性：易于人的理解。
- 健壮性：有很好的容错性，能够对不合理的数据进行检查。
- 高效率和低存储量需求：时间复杂度低和空间复杂度低。
算法中基本操作的执行次数。
时间复杂度可写作 T(n)。
计算步骤如下：
- 确定算法中记得基本操作、问题的规模 N。
- 根据基本操作执行情况计算出规模 N 的函数 f(N)，找出最高阶项，将系数改成 1，即得到时间复杂度。
算法在运行过程中临时占用存储空间大小。