Algorithmic efficiency
Python for AP CS Principles Lesson 11 1:55 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Two programs can both be correct and still take wildly different amounts of time, so we need a way to compare them.
两个程序可以都是对的，花的时间却相差极大， 所以我们需要一种比较它们的办法。
We measure an algorithm by how many steps it does.
我们衡量一个算法，看的是它做了多少"步"。
Here the count follows the list size exactly — ten, twenty, forty.
这里的步数正好跟着列表大小走——10、20、40。
Seconds would depend on which computer you ran it on; counting steps does not.
秒数取决于你在哪台机器上跑； 而数步数不受这个影响。
Now the question that actually matters: not how many steps, but how fast that number grows.
现在才是真正要紧的问题： 不是做了多少步，而是这个数字"涨得有多快"。
Look at the same three input sizes.
看同样这三种输入规模。
Searching a list grows slowly — double the input, double the work, and it stays reasonable.
在列表里查找涨得很慢——输入翻倍，工作量翻倍，这是合理的。
Trying every possible order grows the other way: at forty items it is a number with forty-eight digits.
而把所有可能的顺序都试一遍，涨的方向完全不同： 到 40 个元素时，那是一个 48 位数。
That is what unreasonable means.
这就是"不合理"的意思。
It blows up.
它爆掉了。
And there are three different kinds of hard, which students often collapse into one.
而"难"有三种，学生常常把它们混成一种。
Fast: it finishes quickly even for big input.
快：就算输入很大，它也很快跑完。
Slow but doable: an algorithm exists, it may just take far too long, so in practice we accept a good-enough answer instead of the perfect one.
慢但做得到：算法是存在的，只是可能要花太久太久， 所以现实中我们退而接受一个"够好"的答案，而不是完美的那个。
And then a third kind, worse than slow: some problems cannot be solved at all.
然后还有第三种，比慢更糟： 有些问题"根本无法被解决"。
Those are called undecidable, and no matter how fast computers get, no program can always give the right answer.
它们叫作不可判定问题， 而无论计算机变得多快， 都没有程序能对每一个输入都给出正确答案。
Four things to take with you.
带走四点。
One: efficiency counts steps, because seconds vary from machine to machine.
第一：效率数的是步数，因为秒数因机器而异。
Two: what matters is how the work grows with input.
第二：要紧的是工作量随输入怎么增长。
Three: a reasonable algorithm scales, an unreasonable one does not.
第三：合理的算法能扩展，不合理的不能。
Four: an undecidable problem has no algorithm at all.
第四：不可判定问题根本没有算法。
Now count some steps in the tasks below.
现在去下面的题里数一数步数。