数据结构与算法 / 系统课时

数据结构与算法解决什么问题

数据结构与算法解决什么问题

学习目标

  • 理解数据结构、算法与程序之间的关系。
  • 能从真实业务需求中识别查找、排序、去重、调度和路径规划问题。
  • 掌握“明确问题、选择结构、设计步骤、分析复杂度、验证边界”的基本方法。
  • 建立工程视角:算法不仅要正确,还要考虑性能、可读性、扩展性和数据规模。
  • 数据结构
    • 线性结构
      • 数组
      • 链表
      • 栈
      • 队列
    • 非线性结构
      • 树
      • 堆
      • 图
    • 映射结构
      • 哈希表
  • 算法
    • 查找
    • 排序
    • 遍历
    • 统计
    • 匹配
    • 调度
    • 路径规划
  • 工程评价维度
    • 正确性
    • 时间复杂度
    • 空间复杂度
    • 稳定性
    • 可维护性
    • 数据规模适配
  • 解决问题的基本流程
    • 明确输入与输出
    • 识别高频操作
    • 选择数据结构
    • 设计处理步骤
    • 分析复杂度
    • 编写测试

问题背景或应用场景

软件系统中的大量问题,表面上属于不同业务,底层却经常可以归纳为相同的数据结构与算法问题。例如,一个电商系统可能包含以下需求:

  1. 根据商品编号快速查询商品。
  2. 按销量、价格或评分对商品排序。
  3. 判断用户是否重复领取优惠券。
  4. 按照创建时间处理订单任务。
  5. 维护用户最近访问的页面记录。
  6. 计算仓库之间的最短配送路径。
  7. 根据分类关系展示多级商品目录。

这些需求分别对应不同的基础问题:

  • 快速查询通常需要数组、哈希表、树或索引结构。
  • 排序需要选择合适的排序算法。
  • 去重通常需要集合或哈希表。
  • 任务处理通常需要队列或优先队列。
  • 最近访问记录可能使用栈、队列或双向链表。
  • 最短路径通常使用图算法。
  • 多级目录通常使用树结构。

如果只会编写业务判断,而不了解底层结构,就容易出现以下问题:

  • 数据量较小时运行正常,数据量增大后接口变慢。
  • 为了查找一个元素,每次都扫描全部数据。
  • 为了插入一个元素,频繁移动大量数据。
  • 为了去重,使用多层循环反复比较。
  • 为了实现调度,编写大量难以维护的条件分支。
  • 算法只在典型输入上正确,一遇到空输入或重复值就出错。

因此,学习数据结构与算法的目标不是记忆大量题目,而是建立一套稳定的分析方法。

核心原理

1. 数据结构解决“数据如何组织”

数据结构描述数据元素的存储方式以及元素之间的关系。例如:

  • 数组按连续位置组织数据,适合根据索引快速访问。
  • 链表通过节点引用连接元素,适合在已知位置附近插入和删除。
  • 栈遵循后进先出,适合撤销、函数调用和表达式求值。
  • 队列遵循先进先出,适合任务排队和消息处理。
  • 哈希表通过键映射到值,适合快速查询和去重。
  • 树表示层级关系,适合目录、组织架构和搜索索引。
  • 图表示多对多关系,适合道路、社交网络和依赖关系。

数据结构不是孤立存在的。选择结构时,需要结合最常见的操作:

  • 读取是否频繁。
  • 插入删除是否频繁。
  • 是否需要保持顺序。
  • 是否需要按键查询。
  • 是否存在层级关系。
  • 是否需要表示多对多连接。
  • 数据规模是否可能持续增长。

2. 算法解决“处理步骤如何设计”

算法是一组明确、有限、可执行的步骤,用于把输入转换为期望输出。一个完整算法通常具备以下特征:

  • 输入明确。
  • 输出明确。
  • 每一步可执行。
  • 每一步没有歧义。
  • 在有限步骤后结束。
  • 对约定范围内的输入都能得到正确结果。

例如,“找出最高分”可以描述为:

  1. 如果列表为空,返回错误。
  2. 把第一个分数作为当前最高分。
  3. 从第二个分数开始依次比较。
  4. 如果当前分数更高,就更新最高分。
  5. 遍历结束后返回最高分。

这段描述就是算法。Python、Java 或 Go 只是算法的具体实现语言。

3. 数据结构与算法必须配合

同一个问题,使用不同的数据结构,算法成本可能完全不同。

假设系统中保存了一百万个用户,需要根据用户编号查询用户:

  • 使用普通列表时,最坏情况下需要检查一百万个元素。
  • 使用哈希表时,通常可以通过编号直接定位。
  • 使用有序数组时,可以使用二分查找缩小范围。
  • 使用数据库时,可以通过索引结构提升查询效率。

因此,算法效率并不只由代码写法决定,也取决于数据如何组织。

4. 工程中的“正确”不只是结果正确

一个算法得到正确结果,并不代表它适合生产环境。工程中通常还需要考虑:

  • 数据规模:输入是 10 个元素还是 1000 万个元素。
  • 响应时间:是否需要在几十毫秒内返回。
  • 内存限制:能否复制全部数据。
  • 并发压力:算法是否会在高并发下放大资源消耗。
  • 稳定性:最坏情况是否可能拖垮系统。
  • 可维护性:代码是否清晰,边界是否明确。
  • 可扩展性:未来增加新规则时是否容易修改。

5. 通用问题分析框架

面对一个新的算法问题,可以按以下顺序分析:

  1. 明确问题目标。
  2. 明确输入和输出。
  3. 确认数据规模和数据特征。
  4. 找出高频操作。
  5. 选择候选数据结构。
  6. 设计处理步骤。
  7. 分析时间复杂度。
  8. 分析空间复杂度。
  9. 设计边界用例。
  10. 编写测试并验证结果。

基础用法

下面以“查找最高分”为例,演示完整分析过程。

第一步:明确输入

输入是一组整数分数,例如:

text
78 92 85 96 88

第二步:明确输出

输出最高分:

text
96

第三步:识别边界

需要考虑:

  • 列表为空。
  • 只有一个分数。
  • 所有分数相同。
  • 分数中包含负数。
  • 最高分出现在第一个位置。
  • 最高分出现在最后一个位置。

第四步:选择结构

本例只需要顺序读取所有分数,使用列表即可。

第五步:设计算法

使用一个变量保存当前最高分,逐个扫描剩余元素。

第六步:分析成本

如果有 n 个分数,最多需要比较 n - 1 次,因此时间复杂度为 O(n)。

算法只使用固定数量的变量,因此辅助空间复杂度为 O(1)。

完整可运行示例

python
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()

运行命令:

bash
python lesson_01_01.py

预期输出

text
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

示例分析

对于第一组数据:

text
78 92 85 96 88

执行过程如下:

text
初始最高分:78
比较 92:更新为 92
比较 85:保持 92
比较 96:更新为 96
比较 88:保持 96
最终结果:96

该算法不会依赖分数是否有序,也不会创建与输入规模相同的新容器,因此适合作为线性扫描的基础示例。

Tips

  • 先明确输入和输出,再开始写代码。
  • 先保证正确性,再讨论优化。
  • 数据结构应围绕高频操作选择,而不是根据熟悉程度选择。
  • 简单方案在数据规模较小时通常更容易维护。
  • 复杂度相同的两个算法,实际运行速度仍可能不同。
  • 异常输入处理属于算法契约的一部分。
  • 对外提供函数时,应明确是否允许修改输入数据。
  • 生产环境中需要同时关注平均性能和最坏性能。
  • 数据库索引、缓存、消息队列等工程组件,本质上也大量使用数据结构与算法思想。

常见错误

错误一:把数据结构等同于变量类型

整数、字符串和布尔值是基础数据类型。数组、链表、栈、队列、树和图才是本课程重点讨论的数据组织方式。

错误二:只关注代码能否运行

代码能运行不代表算法正确,也不代表在大规模数据下可接受。

错误三:看到循环就认为性能差

循环本身不是问题。关键在于循环次数如何随输入规模增长。

错误四:忽略数据特征

有序数据、重复数据、稀疏数据和动态变化数据,适合的结构可能不同。

错误五:过早优化

在需求、规模和瓶颈都不明确时,使用复杂结构可能增加维护成本。

错误六:没有定义边界行为

例如空列表是返回空值、返回默认值还是抛出异常,必须提前约定。

本课练习

  1. 实现一个函数,返回最低分。
  2. 实现一个函数,同时返回最高分和最低分。
  3. 实现一个函数,返回最高分第一次出现的位置。
  4. 实现一个函数,统计及格人数,及格线由参数传入。
  5. 使用集合对用户编号去重,并说明为什么集合适合去重。
  6. 思考以下业务分别适合什么结构:
    • 浏览器后退。
    • 打印任务排队。
    • 根据用户编号查用户。
    • 展示公司组织架构。
    • 计算城市之间的路线。
  7. 为最高分函数补充以下测试:
    • 空列表。
    • 单元素列表。
    • 所有元素相同。
    • 全部为负数。
    • 最高分位于首位。
    • 最高分位于末尾。
按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

数据结构与算法解决什么问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通