我们要做什么
- 两个程序可能都正确,但花费的时间却差别很大。
- 这节课讲效率:当输入变大时,工作量怎样增长。
- 边读边思考这些想法;然后用几个小任务,自己来数一数步数。
计算工作量
- 我们用做了多少步来衡量一个算法,而不是用秒。
- 用秒来算取决于电脑;数步数则不会。
- 输入越多,通常步数越多。问题是:多多少。
合理与不合理的运行时间
- 合理时间指步骤数量随多项式或更慢的速度增长:常数、线性、平方或立方。
- 单个循环是线性的。嵌套循环是平方级(n × n)。平方级比线性增长快,但仍属于合理时间。
- 不合理时间指指数级或阶乘级增长。输入稍有增加,工作量就会激增。
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
一个小演示:数步数
- 下面我们数一次线性搜索做了多少次比较。
- 这个数量随列表大小同步增长 —— 缓慢、稳定地增长。
- 试着改变大小,看看这个数量跟着变。
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))
当"快"还不够时
- 有些问题没有已知的合理时间算法。
- 精确方法可能尝试所有排列。这是阶乘级增长,因此对于大输入而言是不合理的。
- 启发式是一种捷径,可提供足够好的答案。它不保证是最优解。你无需记忆某一种特定的启发式方法。
不可判定问题
- 比慢更糟的是:有些问题根本无法被任何算法解决。
- 这些叫作不可判定(undecidable)问题。
- 不论电脑变得多快,没有程序能对每个输入都给出正确答案。
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
要记住的关键点
- 效率关注的是步骤数如何随输入规模增长,而非单台计算机花费多少秒。
- 多项式级或更低的增长属于合理时间。嵌套循环(n × n)仍属合理。
- 指数级或阶乘级增长是不合理的。某些问题甚至不可判定。
常见错误
- 将嵌套循环视为不合理是错误的。平方级和立方级增长仍属合理时间。
- 以形式化Big-O记号作为考试规则。Big-O本身不考。关键在于判断是多项式级或更低,还是指数级或阶乘级。
现在轮到你
- 写一些小函数来数步数,亲身感受工作量如何增长。
- 比较单层循环、嵌套循环和“尝试所有顺序”。嵌套循环在合理时间内仍可完成。按检查答案按钮。
How algorithms scale
Square growth rises faster than a straight line, and it is still reasonable time. Factorial growth is unreasonable.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
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.
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
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.
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
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.
点击“运行”查看此处输出。