# 秒表量不出算法：一条百万程序员的入门神课深读 ## 概述 “这段代码有点慢”——程序员每天都说这句话，但很少有人能说清“慢”到底该怎么量。拿秒表测运行时间？机器一换、语言一换、输入一变，数字全变。真正解决问题的工具只有一个：Big O 记号。它是所有程序员面试绕不开的概念，也是最多人“以为自己懂了、一写就露馅”的概念。 本文深读的，是 YouTube 上讲这个概念最经典的入门视频之一——CS Dojo 频道的《Introduction to Big O Notation and Time Complexity》。这是《数据结构与算法》（Data Structures & Algorithms）系列的第七讲，长期被视为“第一次真正听懂 Big O”的那节课：不堆数学符号，用一个又一个代码小例子，把“增长率”这个抽象概念讲到直觉化。本文按视频的叙事顺序拆解它的论证结构，补上它背后的数学史与理论脉络，再对它的简化口径做一次批判性审查——让你没看过视频也能懂，看过视频能懂得更深。 ## 视频基本信息 | 项目 | 内容 | |------|------| | 视频标题 | Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7) | | 中文译名 | 大O记号与时间复杂度入门（《数据结构与算法》系列第7讲） | | 频道 | CS Dojo（主理人 YK Sugi，据其频道自述曾为 Google 工程师） | | 发布时间 | 2018年（据频道页面，未能实时核实具体日期） | | 播放量 | 数百万量级（据频道页面历史口径；实时数据以频道页为准） | | 形式 | 图示讲解为主，配伪代码/Python 式小例子，时长十余分钟 | | 观看方式 | YouTube 搜索 "CS Dojo Big O Notation"，或见文末参考来源 | 需要说明：本文写作时未能实时抓取频道页面，播放量与发布日期均为历史口径，请以频道页面实时显示为准。频道本身的定位在业内并无争议——这是 YouTube 上最知名的“数据结构与算法友好讲解”频道之一，Python 为主的低门槛风格让它在零基础观众中口碑极高。 ## 核心主张拆解 整条视频的论证是一条干净的单线程：**先拆掉“秒表思维”，再立起“增长思维”，最后给出化简规则**。按叙事顺序拆成五步。 ### 第一步：秒表为什么不可靠 视频的起点不是定义，而是一个否定：**用实际运行时间比较两个算法的好坏，是不可靠的**。原因有三个。其一，机器不同——同一份代码在手机和服务器上跑出的时间可以差几十倍；其二，语言不同——Python 和 C 实现同一个逻辑，常数开销完全不在一个量级；其三，输入不同——给一个已经排好序的数组和给一个乱序数组，同一个排序算法表现天差地别。 这个开头看似平淡，实际上完成了一次“度量衡的转换”：它把读者的注意力从“这段代码在我电脑上跑了几毫秒”，强制切换到“这段代码的运行时间**随输入怎么变化**”。前者是工程的测量问题，后者才是算法的数学问题。Big O 的一切，都建立在这个切换之上。 ### 第二步：真正该问的问题是“输入变大，会怎样” 拆掉秒表之后，视频立起替代品：**增长率（growth rate）**。不问你跑了多久，只问你：输入规模 n 翻倍时，你的运行时间变成了几倍？ 如果和 n 无关，那是常数时间 O(1)——比如按索引取数组元素。如果 n 翻倍、时间也大致翻倍，那是线性时间 O(n)——比如遍历一遍数组找最大值。如果 n 翻倍、时间变成四倍，那是平方时间 O(n²)——典型的两层嵌套循环。如果 n 翻倍、时间只多了一步，那是对数时间 O(log n)——比如二分查找，每次比较把搜索空间砍一半。 视频在这里放出了全片最有冲击力的东西：**几条增长曲线画在同一张图上**。n 很小时，各条曲线挤在一起，看不出高下；n 一大，O(n²) 的曲线垂直起飞，把 O(n log n)、O(n) 远远甩开。这张图解释了一个反直觉的事实：**为什么算法好坏只在小输入上“感觉不到”，却在大输入上“生死攸关”**——你本地测试用的 100 条数据永远暴露不了 O(n²)，上线后的 1000 万条数据会替你暴露。 ### 第三步：化简规则——去常数、留主项 有了增长率，接下来是 Big O 的两条核心化简规则。**第一条：常数因子不算数**。一个跑 2n 次的循环和一个跑 n 次的循环，增长率相同，都记作 O(n)——因为“2 倍”这种常数差异，换个机器、换个语言就可能消失，它不属于算法本身的性质。**第二条：只留最大项**。一个 O(n² + n) 的算法，当 n 足够大时，n² 完全碾压 n（n=1000 时，n² 是一百万，n 只有一千），所以记作 O(n²)。 这两条规则是初学者最容易心理不适的地方：“凭什么 2n 和 n 算一样？”视频给出的答案和数学史给出的答案一致：Big O 的目的不是预测运行时间，而是**刻画算法在极限下的可扩展性**。一旦接受这个目的，常数和低阶项被舍弃就不是偷懒，而是精准。 ### 第四步：从代码反推复杂度 理论讲完，视频回到程序员最熟悉的场景：给你一段代码，怎么读出它的复杂度。经验法则非常机械——看循环嵌套的层数和每层缩小的方式。单层跑 n 次的循环是 O(n)；两层嵌套、每层 n 次，是 O(n²)；循环变量每次翻倍或减半，是对数因子；不依赖 n 的语句是常数。二分查找就是“循环变量减半”的教科书案例：一百万个数最多只要约 20 次比较，因为 2 的 20 次方刚超过一百万。 ### 第五步：复杂度的“分层表” 视频最后把常见复杂度从快到慢排成一张表：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。这张表的价值在于它给了程序员一套“体感语言”：看见排序，该想到 O(n log n)；看见两层嵌套遍历，该想到 O(n²)；看见“所有子集”，该想到指数级爆炸。面试里常说的“这道题能不能优化”，本质就是问“你能不能在这张表上往左挪一格”。 ## 知识与理论溯源 视频把 Big O 讲得平易近人，但这套记号的历史和理论根基远比视频深。补上这一层，才算“多懂一层”。 **Big O 的数学出身比计算机早了半个多世纪。** O 记号由德国数论家保罗·巴赫曼（Paul Bachmann）在 1894 年的《解析数论》（Die Analytische Zahlentheorie）中首次引入，后经埃德蒙·兰道（Edmund Landau）在解析数论中系统推广，因此数学界至今称它“兰道记号”。它原本是用来描述函数在极限附近的性态、估计素数分布误差的工具——跟计算机毫无关系。直到计算机科学诞生，分析算法复杂度的需求出现，这套数论工具才被“征用”。 **把它变成 CS 标准工具的是高德纳（Donald Knuth）。** 他在 1968 年开始的《计算机程序设计艺术》（The Art of Computer Programming）中系统使用渐近分析来刻画算法，并在 1976 年发表了著名论文《Big Omicron and Big Omega and Big Theta》（ACM SIGACT News），厘清了三个记号的分工：大 O 只保证**上界**（“不会比这更糟”），大 Ω 只保证**下界**（“至少这么糟”），大 Θ 才是**紧确界**（“恰好这个量级”）。高德纳在这篇论文里倡议全行业统一用法——今天算法教材（如 CLRS《算法导论》第三章“函数的增长”）的记号体系，就是这次标准化的成果。 **视频里“代码反推复杂度”的例子，每一个都有真实出处。** 二分查找的 O(log n) 可以追溯到 1940 年代就已实现的经典算法；视频隐含提到的排序下界——基于比较的排序不可能快于 O(n log n)——是决策树模型下的经典定理；而视频中使用的 Python 语言，其内置排序正是蒂姆·彼得斯（Tim Peters）在 2002 年设计的 Timsort，最坏情况 O(n log n)，据 Python 官方文档记载至今仍是 CPython 的标准实现。你今天调用 `list.sort()` 时，跑的就是这套被渐近分析设计过的算法。 **“增长阶决定可扩展性”的思想，还有一个更凝练的表述。** 瑞士计算机科学家尼克劳斯·维尔特（Niklaus Wirth，Pascal 语言之父）1976 年的著作书名就是那句名言：《算法 + 数据结构 = 程序》。算法分析的整个学科，回答的都是这本书封面上没写的那半句——“选哪种结构，代价随输入如何增长”。 ## 批判性审查 这条视频是入门教学的典范，但入门教学必然做简化。以下几处口径，读者应当知道它的边界在哪里。 **其一，视频把 Big O 口语化成了“增长率”，严格说是把 Θ 讲成了 O。** 按高德纳 1976 年的严格定义，O 只是上界——一个 O(n²) 的算法在技术上“也是” O(n³)，因为上界并不要求贴身。入门视频（包括这条）几乎都直接用 Big O 表示“恰好这个量级”，这在工程语境里约定俗成、无伤大雅，但在书面证明里是错误的。看懂这条视频的下一步，是把 Θ/Ω/O 三个符号的分工补齐。 **其二，“常数不算数”在数学上成立，在真实机器上要打折扣。** Big O 回答的是 n 趋于无穷时的行为，但现实中的 n 永远是有限的。一个常数因子小 10 倍的 O(n²) 算法，在 n=1000 的场景下完全可能跑赢 O(n log n) 的实现——缓存局部性、分支预测、内存布局都会参与定价（本站此前《代码慢的真相：数据站错了队》一文正是讲的这一层）。所以工程上的正确姿势是：**先用增长阶做方向判断，再用实测做常数校准**，两步缺一不可。视频为了教学主线只讲了第一步，这不是错误，但照单全收会得出“复杂度好就一定快”的错误推论。 **其三，视频以最坏情况为主线，而很多工程决策其实取决于平均情况。** 快速排序最坏 O(n²)、平均 O(n log n)，这个平均不是安慰奖——配合随机选取基准，最坏情况的概率可以被压到工程上可忽略。类似的还有哈希表的期望 O(1)、动态数组 append 的摊还 O(1)。这些“另一种时间账本”（期望、摊还、最坏）是渐近分析内部的三种不同口径，入门视频通常只点最坏情况一种。读者应当把“某个算法是 O(几)”这个问题理解成“在哪种口径下”。 **其四，视频没有触及“分析的下界”这一半学科。** 它教你证明“我的算法是 O(n log n)”，但没有教你证明“没有算法能比 O(n log n) 更快”——后者（下界证明）才是算法分析里更难、也更深刻的一半。这不是入门课的义务，但值得作为下一步的学习路标。 总体评价：这条视频的核心论证——秒表不可靠、增长率才是本质、去常数留主项——证据充分，是教科书级的标准口径，没有任何被夸大的主张。它的“简化”都发生在上述可预期的教学边界内，属于负责任的简化。 ## 认知提升与实用启示 **第一条：写代码前先问三个问题——n 多大？循环几层？数据有没有“结构”？** n 是一万以内还是一千万量级，直接决定你能不能对 O(n²) 睁一只眼闭一只眼；循环嵌套层数是最快读出复杂度的方式；而数据是否有序、有没有索引、能不能转成哈希查找，决定了你有没有“往左挪一格”的机会。日常开发里绝大多数性能问题，靠降一阶解决，而不是靠微优化解决。 **第二条：把“有点慢”升级成增长阶语言。** 在 code review 和面试里，“这里两层嵌套循环，输入翻倍成本翻四倍，数据量上来会出事”远比“这里有点慢”有说服力——前者是可验证的结构判断，后者是感受。反过来，当你反驳一个过度优化方案时，“这个函数只跑 10 次，优化它省不出一秒”也是增长阶思维的一部分：**找 Biggest O，不是找任何 O**——先优化复杂度最高、输入最大的那一段。 **第三条：用一个土办法实验替代秒表迷信。** 把输入规模乘 10，测一次耗时：耗时约乘 10 是线性，乘 100 是平方，几乎不变是对数或常数。这个“拉伸测试”不需要任何数学，却能快速验证你对一段代码复杂度的猜想——它测的不是时间，而是增长率本身，正好绕开了机器、语言、常数这些秒表陷阱。 ## 视频论证结构图 ```mermaid flowchart TD A["秒表为何不可靠"] --> B["机器 语言 输入都不同"] B --> C["换对问题
输入变大 时间怎么增长"] C --> D["四种增长直觉"] D --> D1["O(1) 常数"] D --> D2["O(log n) 对数"] D --> D3["O(n) 线性"] D --> D4["O(n²) 平方"] D1 --> E["化简规则
去常数 留主项"] D2 --> E D3 --> E D4 --> E E --> F["与机器无关的算法标尺"] F --> G["教学边界
常数 缓存 口径 仍影响实战"] ``` ## 延伸阅读 1. **MIT 6.006《算法导论》公开课（MIT OpenCourseWare）**——第一周的课程把这条视频里“感性”的增长阶，用数学定义和证明严格化，是自然的下一站。 2. **CS Dojo《数据结构与算法》系列其余各讲**——第七讲建立的增长阶语言，会在该系列后续的栈、队列、二叉树各讲中被反复使用。 ## 参考来源 1. [Introduction to Big O Notation and Time Complexity — CS Dojo（YouTube 检索页）](https://www.youtube.com/results?search_query=CS+Dojo+Introduction+to+Big+O+Notation+and+Time+Complexity) — 本文深读的主视频，播放数据以频道页面实时显示为准。 2. [CS Dojo 频道主页](https://www.youtube.com/c/CSDojo) — YK Sugi 的数据结构与算法讲解频道。 3. [Big O notation - Wikipedia](https://en.wikipedia.org/wiki/Big_O_notation) — O 记号的历史（巴赫曼 1894、兰道推广）与严格定义，本文溯源部分的主要交叉来源。 4. [MIT 6.006 Introduction to Algorithms - MIT OpenCourseWare](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/) — 渐近分析的大学标准课程，延伸阅读首选。 5. [Python Sorting HOW TO - Python 官方文档](https://docs.python.org/3/howto/sorting.html) — 记载 CPython 内置排序采用 Timsort（Tim Peters，2002）。 --- > 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 > 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。 > [!tip] 51学通信知识星球 > **星主：爱卫生**（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 > **星球定位**：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 > **当前规模**：5200 篇主题 / 990 个回答，198 元/年。 > **加入福利**：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 > **AI 加持**：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。