Informal Run-Time Analysis · 非正式运行时间分析
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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ì |
Counting the work
- We measure a program's run time 运行时间 by how many times its key statements run.
- Not seconds (those vary by machine) — a count of operations as the input grows.
- More operations for the same input size → slower algorithm.
- This lets us compare algorithms fairly, independent of hardware.
计算工作量
- 我们用关键语句运行多少次来度量程序的运行时间。
- 不是秒（那因机器而异）——而是随输入增长的操作次数。
- 相同输入规模下操作越多 → 算法越慢。
- 这让我们能公平地比较算法，与硬件无关。
A single loop: about n
- A loop over
nitems runs its body aboutntimes. - Double the input → about double the work. This is linear 线性 growth.
- Summing an array, searching a list one-by-one: all about
nsteps. - Written informally as "order
n."
单个循环：约 n
- 对
n个项的循环把它的主体运行约n次。 - 输入翻倍 → 工作约翻倍。这是线性增长。
- 对数组求和、逐个搜索一个列表：都是约
n步。 - 非正式地写作“
n阶”。
A nested loop: about n²
- A nested loop over
nitems runs its inner body aboutn × n = n²times. - Double the input → about four times the work. This is quadratic 二次 growth.
- Comparing all pairs, filling an
n × ngrid: aboutn²steps. n²grows much faster thannasngets large.
嵌套循环：约 n²
- 对
n个项的嵌套循环把它的内层主体运行约n × n = n²次。 - 输入翻倍 → 工作约四倍。这是二次增长。
- 比较所有配对、填满一个
n × n网格：约n²步。 - 当
n变大，n²比n增长快得多。
Comparing growth
- To compare algorithms, ask how the work grows as the input grows.
- For large
n, annalgorithm beats ann²algorithm — often by a lot. - Focus on the part of the code that runs the most (usually the innermost loop).
- The fastest-growing term dominates the total run time.
比较增长
- 要比较算法，问工作如何随输入增长。
- 对大的
n，一个n算法胜过一个n²算法——往往胜很多。 - 聚焦于运行最多的那部分代码（通常是最内层循环）。
- 增长最快的项主导总运行时间。
Judge run time by GROWTH, not a fixed count. An algorithm that does n steps and one that does 2n + 5 steps both grow linearly — for comparing, the constant and the +5 don't matter; the shape (n vs n²) does. A single loop is about n; a nested loop is about n², which grows far faster for large inputs.
用增长判断运行时间，而非一个固定的次数。一个做 n 步的算法和一个做 2n + 5 步的算法都线性增长——对比较而言，常数和 +5 无关紧要；重要的是形状（n 对 n²）。单个循环约为 n；嵌套循环约为 n²，对大输入增长快得多。
Two ways to find duplicates in n items:
- Nested loops comparing every pair: about
n²steps. - Sort first, then one pass: far fewer steps for large
n. - For
n = 1000,n²is a million steps — then²approach is much slower.
在 n 个项里找重复的两种方式：
- 嵌套循环比较每一对：约
n²步。 - **先排序，再一遍扫过：**对大的
n步数少得多。 - 对
n = 1000，n²是一百万步——n²方法慢得多。
Informal run-time analysis counts how many times statements run as the input grows. A single loop over n items is about n (linear); a nested loop is about n² (quadratic), which grows much faster. Compare algorithms by their growth, focusing on the most-executed (innermost) code.
非正式的运行时间分析计算语句随输入增长运行多少次。对 n 个项的单个循环约为 n（线性）；嵌套循环约为 n²（二次），增长快得多。用增长比较算法，聚焦于运行最多的（最内层）代码。
How the work grows with n · 工作如何随 n 增长
A nested loop (n²) grows far faster than a single loop (n). · 嵌套循环（n²）比单个循环（n）增长快得多。
A single loop over n items runs its body about how many times? · 对 n 个项的单个循环把它的主体运行大约多少次？
One loop over n items → about n steps (linear). · 对 n 个项的一个循环 → 约 n 步（线性）。
A nested loop over n items runs its inner body about how many times? · 对 n 个项的嵌套循环把它的内层主体运行大约多少次？
n × n = n² (quadratic). · n × n = n²（二次）。
For n = 1000, about how many steps is an n² algorithm (in millions)? · 对 n = 1000，一个 n² 算法大约多少步（以百万计）？
1000² = 1,000,000 = 1 million. · 1000² = 1,000,000 = 一百万。
For large n, an n-step algorithm is generally faster than an n²-step one. · 对大的 n，一个 n 步算法通常比一个 n² 步的快。
n² grows much faster, so it does far more work at large n. · n² 增长快得多，所以在大 n 时做的工作多得多。
We measure run time in seconds, which is the same on every computer. · 我们用秒来度量运行时间，这在每台计算机上都相同。
We count operations vs. input size — seconds vary by machine. · 我们计算操作数相对于输入规模——秒因机器而异。