Algorithmic Efficiency · 算法效率
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | 算法效率 | suàn fǎ xiào lǜ |
| slow/sləʊ/ | 缓慢 | huǎn màn |
| steps/steps/ | 步骤 | bù zhòu |
| reasonable/ˈriːzənəbl/ | 合理 | hé lǐ |
| unreasonable/ʌnˈriːzənəbl/ | 不合理 | bù hé lǐ |
| heuristic/hjuːˈrɪstɪk/ | 启发式方法 | qǐ fā shì fāng fǎ |
Correct isn't always good enough
- Two algorithms can both be correct, yet one may be far better to use.
- Algorithmic efficiency 算法效率 compares algorithms by the resources they use — mainly time and memory.
- A correct-but-slow algorithm can be useless on large inputs.
- So we need a way to compare how they scale.
正确未必够好
- 两个算法能都正确,但一个可能好用得多。
- 算法效率(algorithmic efficiency)按算法使用的资源比较它们——主要是时间和内存。
- 一个正确但慢的算法在大输入上可能没用。
- 所以我们需要一种方式来比较它们如何扩展。
Algorithmic efficiency compares algorithms by: · 算法效率按什么比较算法:
Efficiency is about time and memory as input grows. · 效率是关于输入增长时的时间和内存。
Counting steps as n grows
- Estimate the number of steps 步骤 an algorithm takes as its input size $n$ grows.
- A linear search takes about $n$ steps; a binary search about $\log_2 n$; comparing every pair about $n^2$.
- As $n$ gets large, these differences become huge.
- The shape of the growth matters far more than a stopwatch.
随 n 增长计步
- 估计一个算法随其输入大小 $n$ 增长所用的步骤(steps)数。
- 线性搜索约用 $n$ 步;二分搜索约 $\log_2 n$;比较每一对约 $n^2$。
- 随着 $n$ 变大,这些差异变得巨大。
- 增长的形状远比秒表重要。
How running time grows with n · 运行时间如何随 n 增长
Slide n and compare the curves: log n stays almost flat, n rises steadily, n² explodes. This is why we compare algorithms by how they scale, not with a stopwatch. · 滑动 n 并比较曲线:log n 几乎保持平坦,n 稳步上升,n² 爆炸。这就是为什么我们按算法如何扩展来比较它们,而非用秒表。
Match each algorithm to its rough number of steps for input size n. · 把每个算法与它对输入大小 n 的大致步骤数配对。
These growth rates decide which algorithm scales. · 这些增长率决定哪个算法能扩展。
Which growth is considered unreasonable as n gets large? · 随 n 变大,哪种增长被认为是不合理的?
Exponential growth quickly becomes far too slow. · 指数增长很快变得太慢。
When an exact answer is too slow, a ______ finds a good-enough solution fast. · 当精确答案太慢,一个______快速找到一个足够好的解。
A heuristic trades a perfect answer for speed. · 启发式方法用完美答案换取速度。
Reasonable vs unreasonable
- We separate a reasonable 合理 running time from an unreasonable 不合理 one.
- Roughly, growth like $n$ or $n^2$ is reasonable; doubling steps per extra item (like $2^n$) is not.
- When an exact answer is too slow, use a heuristic 启发式方法 — a good-enough solution found fast.
- Not perfect, but useful when perfect is impossible in time.
合理与不合理
- 我们区分合理(reasonable)的运行时间和不合理(unreasonable)的。
- 大致来说,像 $n$ 或 $n^2$ 的增长是合理的;每多一项就翻倍步骤(像 $2^n$)则不是。
- 当精确答案太慢,用一个启发式方法(heuristic)——快速找到的一个足够好的解。
- 不完美,但当完美在时间上不可能时有用。
A binary search of 1,000,000 sorted items needs at most about how many steps? (2^20 ≈ a million) · 一个 1,000,000 项已排序的二分搜索最多约需多少步?(2^20 ≈ 一百万)
Because 2^20 is just over a million, ~20 halvings suffice. · 因为 2^20 刚过一百万,约 20 次减半就够。
A correct algorithm can still be too slow to use on large inputs. · 一个正确的算法在大输入上仍可能太慢而无法使用。
It must also finish in a reasonable time. · 它还必须在合理时间内完成。
Too slow to use
- This is why some correct algorithms are too slow 缓慢 to run in practice on large inputs.
- Being correct is not enough — an algorithm must also finish in a reasonable time.
A million items. A linear search of 1,000,000 sorted items may take up to 1,000,000 steps. A binary search takes at most about 20, because $2^{20}$ is just over a million. On small lists the gap barely matters; on a million items, binary is the only reasonable choice.
太慢而无法使用
- 这就是为什么一些正确的算法在大输入上太缓慢(slow)而无法在实践中运行。
- 正确不够——一个算法还必须在合理时间内完成。
一百万项。 一个 1,000,000 项已排序的线性搜索可能用多达 1,000,000 步。一个二分搜索最多约 20 步,因为 $2^{20}$ 刚过一百万。在小列表上差距几乎无所谓;在一百万项上,二分是唯一合理的选择。
Algorithmic efficiency compares algorithms by resources as input size $n$ grows: linear $n$, binary $\log_2 n$, all-pairs $n^2$. Growth like $n$ or $n^2$ is reasonable; $2^n$ is unreasonable (use a heuristic). A correct algorithm that is too slow on large inputs is not good enough.
算法效率随输入大小 $n$ 增长按资源比较算法:线性 $n$、二分 $\log_2 n$、每一对 $n^2$。像 $n$ 或 $n^2$ 的增长是合理的;$2^n$ 是不合理的(用一个启发式方法)。一个在大输入上太缓慢的正确算法不够好。