Algorithmic efficiency · 算法效率
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
我们要做什么
- 两个程序可能都正确,但花费的时间却差别很大。
- 这节课讲效率:当输入变大时,工作量怎样增长。
- 边读边思考这些想法;然后用几个小任务,自己来数一数步数。
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
计算工作量
- 我们用做了多少步来衡量一个算法,而不是用秒。
- 用秒来算取决于电脑;数步数则不会。
- 输入越多,通常步数越多。问题是:多多少。
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
合理与不合理的运行时间
- 有些算法增长得慢:输入翻倍,工作量大约也翻倍。
- 有些算法增长得快:输入只多一点,工作量就猛增。
- "合理"的运行时间增长得够慢,能够完成;"不合理"的则会爆炸式增长。
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
一个小演示:数步数
- 下面我们数一次线性搜索做了多少次比较。
- 这个数量随列表大小同步增长 —— 缓慢、稳定地增长。
- 试着改变大小,看看这个数量跟着变。
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
当"快"还不够时
- 有些问题没有已知的快速算法。
- 唯一的方法要尝试大量的可能性 —— 对大输入来说太慢了。
- 对这些问题,我们常常接受一个够好的答案,而不是完美的答案。
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
不可判定问题
- 比慢更糟的是:有些问题根本无法被任何算法解决。
- 这些叫作不可判定(undecidable)问题。
- 不论电脑变得多快,没有程序能对每个输入都给出正确答案。
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
要记住的关键点
- 效率讲的是工作量如何随输入大小增长。
- 增长慢的算法能扩展到大输入;增长快的则不能。
- 有些问题不合理到无法精确求解,还有些问题是不可判定的。
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
常见错误
- 大 O 描述运行时间如何随输入规模增长。
- 合理时间的算法能扩展;不合理的不能。
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
现在轮到你
- 写一些小函数来数步数,亲身感受工作量如何增长。
- 比较单层循环、嵌套循环,以及"尝试所有顺序"。按检查答案。
How algorithms scale · 算法如何随规模增长
As input grows, O(n²) explodes while O(log n) barely moves. · 随着输入变大,O(n²) 会爆炸式增长,而 O(log n) 几乎不动。
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2. · 编写 scan_compares(data, target),返回一次线性搜索做了多少次比较。把每个元素与 target 比较,每次计数加一,一找到就停止。如果不在列表里,就比较了每个元素。例如:scan_compares([5, 8, 2], 8) → 2。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop. · 编写 pair_count(n),用一个循环嵌套在另一个循环里(两个都遍历 range(n)),返回内层一步执行了多少次。这等于 n × n。例如:pair_count(3) → 9。它比单层循环增长快得多。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · 编写 count_orderings(n),返回 n 个元素能排成多少种不同的顺序 —— 也就是 1 × 2 × ... × n(n 的阶乘)。count_orderings(0) 为 1。例如:count_orderings(3) → 6。注意它爆炸得多快:count_orderings(10) 超过三百万。
Click Run to see the output here. · 点击“运行”查看此处输出。