词汇
| English | 释义 | 拼音 |
|---|---|---|
| run time/rʌn taɪm/ | 运行时间 | yùn xíng shí jiān |
| linear/ˈlɪnɪə/ | 线性 | xiàn xìng |
| quadratic/kwɒˈdrætɪk/ | 二次 | èr cì |
计算工作量
- 我们用关键语句运行多少次来度量程序的运行时间。
- 不是秒(那因机器而异)——而是随输入增长的操作次数。
- 相同输入规模下操作越多 → 算法越慢。
- 这让我们能公平地比较算法,与硬件无关。
单个循环:约 n
- 对
n个项的循环把它的主体运行约n次。 - 输入翻倍 → 工作约翻倍。这是线性增长。
- 对数组求和、逐个搜索一个列表:都是约
n步。 - 非正式地写作“
n阶”。

运行时间如何随元素数量 n 增长
嵌套循环:约 n²
- 对
n个项的嵌套循环把它的内层主体运行约n × n = n²次。 - 输入翻倍 → 工作约四倍。这是二次增长。
- 比较所有配对、填满一个
n × n网格:约n²步。 n²的增长速度远快于n,随着n变得很大。
比较增长
- 要比较算法,问工作如何随输入增长。
- 对大的
n,一个n算法胜过一个n²算法——往往胜很多。 - 聚焦于运行最多的那部分代码(通常是最内层循环)。
- 增长最快的项主导总运行时间。
注意
用增长判断运行时间,而非一个固定的次数。一个做 n 步的算法和一个做 2n + 5 步的算法都线性增长——对比较而言,常数和 +5 无关紧要;重要的是形状(n 对 n²)。单个循环约为 n;嵌套循环约为 n²,对大输入增长快得多。
例子
在 n 个项里找重复的两种方式:
- 嵌套循环比较每一对:约
n²步。 - **先排序,再一遍扫过:**对大的
n步数少得多。 - 对
n = 1000,n²是一百万步——n²方法慢得多。
关键点
非正式的运行时间分析计算语句随输入增长运行多少次。对 n 个项的单个循环约为 n(线性);嵌套循环约为 n²(二次),增长快得多。用增长比较算法,聚焦于运行最多的(最内层)代码。
探索
工作如何随 n 增长
嵌套循环(n²)比单个循环(n)增长快得多。
练习
对 n 个项的单个循环把它的主体运行大约多少次?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
对 n 个项的一个循环 → 约 n 步(线性)。
练习
对 n 个项的嵌套循环把它的内层主体运行大约多少次?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
n × n = n²(二次)。
练习
对 n = 1000,一个 n² 算法大约多少步(以百万计)?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
1000² = 1,000,000 = 一百万。
练习
对大的 n,一个 n 步算法通常比一个 n² 步的快。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
n² 增长快得多,所以在大 n 时做的工作多得多。
练习
我们用秒来度量运行时间,这在每台计算机上都相同。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
我们计算操作数相对于输入规模——秒因机器而异。