01-数据结构概念

程序设计 = 数据结构 + 算法

1 数据结构

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

1.1 基本概念

• 数据：能别计算机识别、处理的符号集合
• 数据对象：性质相同的数据元素的集合，是数据的子集。
• 数据元素：组成数据的、有一定意义的基本单位。通常作为整体被计算机处理。
• 数据项：数据元素可由多个数据项组成，数据项是数据不可分割的最小单位

graph TD
数据-->数据对象
数据对象-->数据元素1
数据元素1-->数据项1
数据元素1-->数据项2
数据对象-->数据元素2
数据元素2-->数据项3
数据元素2-->数据项4

1.2 逻辑结构和物理结构

逻辑结构

数据对象中数据元素之间的相互关系。

• 集合结构：结构中的数据元素出了同属于一个集合外，没有其他关系
• 线性结构：一对一
• 树结构：一对多
• 图结构：多对多

物理结构

数据的逻辑结构在计算机中的存储形式

• 顺序存储结构
• 链式存储结构

2 算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

2.1 算法的特性

算法具有五个基本特性

• 输入：零个或多个输入
• 输出：一个或多个输出
• 有穷性：执行有限步骤后，在可接受时间内自动结束
• 确定性：没有二义性，相同的输入只能有唯一输出结果
• 可行性：每一步能通过有限次数完成

2.2 算法设计的要求

• 正确性：输入、输出和加工处理无歧义性、能正确反映需求、能得到正确答案
• 可读性：便于阅读、理解和交流
• 健壮性：能够处理不合法输入
• 时间效率高和存储量低

2.3 算法时间复杂度

推导大 O 阶方法

n 是问题规模，对数列运算出执行次数T(n) = O(f(n))

• 用常数 1 取代运行时间中的加法常数。
• 在修改后的运行次数函数中，只保留最高阶项。
• 若最高阶项存在且不是 1， 则去除与这个项相乘的常数。

常见的时间复杂度排序： O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况

没有特殊说明的情况下，都指最坏时间复杂度

2.4 算法空间复杂度

S(n) = O(f(n))。

若算法执行时所需的辅助空间对于输入量而言是个常数，则称此算法为原地工作，空间复杂度 O(1)。