课程 288 / 365
79%
数据结构与算法直觉·理解·10 分钟
正文已完成

复杂度先回答增长趋势

不背公式,先用输入翻倍后的工作量变化理解常数、线性和平方增长。

L288

复杂度描述输入增加时工作量的增长趋势。一次固定读取、逐项扫描和两两比较,会在数据翻倍时呈现完全不同的变化;这个趋势能帮助你找到需要优化的位置。

这一课的结果

能用输入规模增长解释一段流程的大致复杂度趋势。

核心概念

先把关键判断说清楚

01

常数表示不随规模遍历

凭稳定键读取一个映射项通常只做有限步骤,数据翻倍不要求逐项检查。

02

线性表示每项一次

扫描、转换或校验全部记录时,输入翻倍,主要工作量也大致翻倍。

03

平方常见于两两比较

每个元素都与所有其他元素比较时,输入翻倍可能带来约四倍比较,规模稍大就会显著变慢。

案例拆解

联系人去重从两两比对到按键分组

脚本对每个联系人再遍历全部联系人比较邮箱,1 万条数据开始明显卡顿。

  1. 01

    识别当前结构为外层每条记录乘内层全部记录的两两比较。

  2. 02

    改为单次遍历,用规范化邮箱作为映射键收集重复项。

  3. 03

    用 1 千、5 千、1 万条样本记录处理时间,确认增长趋势已接近线性。

案例结果

工作量从随记录数平方增长改为主要随记录数线性增长。

提交前练习

现在轮到你

选一个处理数据的流程,估计输入翻倍后核心步骤会增长多少。

内容会自动保存在当前设备
查看参考答案与评分标准

参考答案

输入 n 为文件数;核心操作是逐文件读取一次,没有嵌套;n 翻倍时读取次数约 2 倍,属于线性趋势;用 100、1,000、10,000 个小文件记录总耗时。

评分标准

  • 输入规模定义明确
  • 增长判断来自代码或流程结构
  • 验证包含多个数量级

本课收口 · 学习证据

完成,不等于随手打一个勾。

确认阅读、保存练习,再用 30 秒检查和一句话总结留下真实学习证据。

0 / 3
02完成本课练习0 / 4 项必填内容已填写
03通过理解检查约 30 秒
一个两层循环让每条记录与全部记录比较,输入翻倍时比较次数大致怎样变化?
你现在更接近哪一种状态?
完成上面三项后,才能把本课记为已验证。

资料来源

继续核对与延伸阅读

本课内容最近更新于