数据结构与算法 / 系统课时
数据结构与算法解决什么问题
数据结构与算法解决什么问题
学习目标
- 理解数据结构、算法与程序之间的关系。
- 能从真实业务需求中识别查找、排序、去重、调度和路径规划问题。
- 掌握“明确问题、选择结构、设计步骤、分析复杂度、验证边界”的基本方法。
- 建立工程视角:算法不仅要正确,还要考虑性能、可读性、扩展性和数据规模。
- 数据结构
- 线性结构
- 数组
- 链表
- 栈
- 队列
- 非线性结构
- 树
- 堆
- 图
- 映射结构
- 哈希表
- 线性结构
- 算法
- 查找
- 排序
- 遍历
- 统计
- 匹配
- 调度
- 路径规划
- 工程评价维度
- 正确性
- 时间复杂度
- 空间复杂度
- 稳定性
- 可维护性
- 数据规模适配
- 解决问题的基本流程
- 明确输入与输出
- 识别高频操作
- 选择数据结构
- 设计处理步骤
- 分析复杂度
- 编写测试
问题背景或应用场景
软件系统中的大量问题,表面上属于不同业务,底层却经常可以归纳为相同的数据结构与算法问题。例如,一个电商系统可能包含以下需求:
- 根据商品编号快速查询商品。
- 按销量、价格或评分对商品排序。
- 判断用户是否重复领取优惠券。
- 按照创建时间处理订单任务。
- 维护用户最近访问的页面记录。
- 计算仓库之间的最短配送路径。
- 根据分类关系展示多级商品目录。
这些需求分别对应不同的基础问题:
- 快速查询通常需要数组、哈希表、树或索引结构。
- 排序需要选择合适的排序算法。
- 去重通常需要集合或哈希表。
- 任务处理通常需要队列或优先队列。
- 最近访问记录可能使用栈、队列或双向链表。
- 最短路径通常使用图算法。
- 多级目录通常使用树结构。
如果只会编写业务判断,而不了解底层结构,就容易出现以下问题:
- 数据量较小时运行正常,数据量增大后接口变慢。
- 为了查找一个元素,每次都扫描全部数据。
- 为了插入一个元素,频繁移动大量数据。
- 为了去重,使用多层循环反复比较。
- 为了实现调度,编写大量难以维护的条件分支。
- 算法只在典型输入上正确,一遇到空输入或重复值就出错。
因此,学习数据结构与算法的目标不是记忆大量题目,而是建立一套稳定的分析方法。
核心原理
1. 数据结构解决“数据如何组织”
数据结构描述数据元素的存储方式以及元素之间的关系。例如:
- 数组按连续位置组织数据,适合根据索引快速访问。
- 链表通过节点引用连接元素,适合在已知位置附近插入和删除。
- 栈遵循后进先出,适合撤销、函数调用和表达式求值。
- 队列遵循先进先出,适合任务排队和消息处理。
- 哈希表通过键映射到值,适合快速查询和去重。
- 树表示层级关系,适合目录、组织架构和搜索索引。
- 图表示多对多关系,适合道路、社交网络和依赖关系。
数据结构不是孤立存在的。选择结构时,需要结合最常见的操作:
- 读取是否频繁。
- 插入删除是否频繁。
- 是否需要保持顺序。
- 是否需要按键查询。
- 是否存在层级关系。
- 是否需要表示多对多连接。
- 数据规模是否可能持续增长。
2. 算法解决“处理步骤如何设计”
算法是一组明确、有限、可执行的步骤,用于把输入转换为期望输出。一个完整算法通常具备以下特征:
- 输入明确。
- 输出明确。
- 每一步可执行。
- 每一步没有歧义。
- 在有限步骤后结束。
- 对约定范围内的输入都能得到正确结果。
例如,“找出最高分”可以描述为:
- 如果列表为空,返回错误。
- 把第一个分数作为当前最高分。
- 从第二个分数开始依次比较。
- 如果当前分数更高,就更新最高分。
- 遍历结束后返回最高分。
这段描述就是算法。Python、Java 或 Go 只是算法的具体实现语言。
3. 数据结构与算法必须配合
同一个问题,使用不同的数据结构,算法成本可能完全不同。
假设系统中保存了一百万个用户,需要根据用户编号查询用户:
- 使用普通列表时,最坏情况下需要检查一百万个元素。
- 使用哈希表时,通常可以通过编号直接定位。
- 使用有序数组时,可以使用二分查找缩小范围。
- 使用数据库时,可以通过索引结构提升查询效率。
因此,算法效率并不只由代码写法决定,也取决于数据如何组织。
4. 工程中的“正确”不只是结果正确
一个算法得到正确结果,并不代表它适合生产环境。工程中通常还需要考虑:
- 数据规模:输入是 10 个元素还是 1000 万个元素。
- 响应时间:是否需要在几十毫秒内返回。
- 内存限制:能否复制全部数据。
- 并发压力:算法是否会在高并发下放大资源消耗。
- 稳定性:最坏情况是否可能拖垮系统。
- 可维护性:代码是否清晰,边界是否明确。
- 可扩展性:未来增加新规则时是否容易修改。
5. 通用问题分析框架
面对一个新的算法问题,可以按以下顺序分析:
- 明确问题目标。
- 明确输入和输出。
- 确认数据规模和数据特征。
- 找出高频操作。
- 选择候选数据结构。
- 设计处理步骤。
- 分析时间复杂度。
- 分析空间复杂度。
- 设计边界用例。
- 编写测试并验证结果。
基础用法
下面以“查找最高分”为例,演示完整分析过程。
第一步:明确输入
输入是一组整数分数,例如:
78 92 85 96 88第二步:明确输出
输出最高分:
96第三步:识别边界
需要考虑:
- 列表为空。
- 只有一个分数。
- 所有分数相同。
- 分数中包含负数。
- 最高分出现在第一个位置。
- 最高分出现在最后一个位置。
第四步:选择结构
本例只需要顺序读取所有分数,使用列表即可。
第五步:设计算法
使用一个变量保存当前最高分,逐个扫描剩余元素。
第六步:分析成本
如果有 n 个分数,最多需要比较 n - 1 次,因此时间复杂度为 O(n)。
算法只使用固定数量的变量,因此辅助空间复杂度为 O(1)。
完整可运行示例
from collections.abc import Sequence
def find_max_score(scores: Sequence[int]) -> int:
if not scores:
raise ValueError("scores cannot be empty")
max_score = scores[0]
for score in scores[1:]:
if score > max_score:
max_score = score
return max_score
def main() -> None:
cases = [
[78, 92, 85, 96, 88],
[100],
[60, 60, 60],
[-5, -2, -10],
]
for index, scores in enumerate(cases, start=1):
result = find_max_score(scores)
print(f"case {index}: scores={scores}, max={result}")
try:
find_max_score([])
except ValueError as error:
print(f"empty case: {error}")
if __name__ == "__main__":
main()运行命令:
python lesson_01_01.py预期输出
case 1: scores=[78, 92, 85, 96, 88], max=96
case 2: scores=[100], max=100
case 3: scores=[60, 60, 60], max=60
case 4: scores=[-5, -2, -10], max=-2
empty case: scores cannot be empty示例分析
对于第一组数据:
78 92 85 96 88执行过程如下:
初始最高分:78
比较 92:更新为 92
比较 85:保持 92
比较 96:更新为 96
比较 88:保持 96
最终结果:96该算法不会依赖分数是否有序,也不会创建与输入规模相同的新容器,因此适合作为线性扫描的基础示例。
Tips
- 先明确输入和输出,再开始写代码。
- 先保证正确性,再讨论优化。
- 数据结构应围绕高频操作选择,而不是根据熟悉程度选择。
- 简单方案在数据规模较小时通常更容易维护。
- 复杂度相同的两个算法,实际运行速度仍可能不同。
- 异常输入处理属于算法契约的一部分。
- 对外提供函数时,应明确是否允许修改输入数据。
- 生产环境中需要同时关注平均性能和最坏性能。
- 数据库索引、缓存、消息队列等工程组件,本质上也大量使用数据结构与算法思想。
常见错误
错误一:把数据结构等同于变量类型
整数、字符串和布尔值是基础数据类型。数组、链表、栈、队列、树和图才是本课程重点讨论的数据组织方式。
错误二:只关注代码能否运行
代码能运行不代表算法正确,也不代表在大规模数据下可接受。
错误三:看到循环就认为性能差
循环本身不是问题。关键在于循环次数如何随输入规模增长。
错误四:忽略数据特征
有序数据、重复数据、稀疏数据和动态变化数据,适合的结构可能不同。
错误五:过早优化
在需求、规模和瓶颈都不明确时,使用复杂结构可能增加维护成本。
错误六:没有定义边界行为
例如空列表是返回空值、返回默认值还是抛出异常,必须提前约定。
本课练习
- 实现一个函数,返回最低分。
- 实现一个函数,同时返回最高分和最低分。
- 实现一个函数,返回最高分第一次出现的位置。
- 实现一个函数,统计及格人数,及格线由参数传入。
- 使用集合对用户编号去重,并说明为什么集合适合去重。
- 思考以下业务分别适合什么结构:
- 浏览器后退。
- 打印任务排队。
- 根据用户编号查用户。
- 展示公司组织架构。
- 计算城市之间的路线。
- 为最高分函数补充以下测试:
- 空列表。
- 单元素列表。
- 所有元素相同。
- 全部为负数。
- 最高分位于首位。
- 最高分位于末尾。