Appendix B  Analysis of Algorithms 附录 B 算法分析

本页译自 Think Python 2e（Allen B. Downey）· Appendix B Analysis of Algorithms。代码块保留英文原文不翻译；正文段段对照，中文块可用右下角按钮隐藏。

This appendix is an edited excerpt from Think Complexity, by Allen B. Downey, also published by O’Reilly Media (2011). When you are done with this book, you might want to move on to that one.

本附录改编自 Allen B. Downey 所著、O’Reilly Media（2011）出版的《Think Complexity》。读完本书后，你也许会想接着读那一本。

Analysis of algorithms is a branch of computer science that studies the performance of algorithms, especially their run time and space requirements. See http://en.wikipedia.org/wiki/Analysis_of_algorithms.

The practical goal of algorithm analysis is to predict the performance of different algorithms in order to guide design decisions.

During the 2008 United States Presidential Campaign, candidate Barack Obama was asked to perform an impromptu analysis when he visited Google. Chief executive Eric Schmidt jokingly asked him for “the most efficient way to sort a million 32-bit integers.” Obama had apparently been tipped off, because he quickly replied, “I think the bubble sort would be the wrong way to go.” See http://www.youtube.com/watch?v=k4RRi_ntQc8.

This is true: bubble sort is conceptually simple but slow for large datasets. The answer Schmidt was probably looking for is “radix sort” (http://en.wikipedia.org/wiki/Radix_sort)¹.

The goal of algorithm analysis is to make meaningful comparisons between algorithms, but there are some problems:

• The relative performance of the algorithms might depend on characteristics of the hardware, so one algorithm might be faster on Machine A, another on Machine B. The general solution to this problem is to specify a machine model and analyze the number of steps, or operations, an algorithm requires under a given model.
• Relative performance might depend on the details of the dataset. For example, some sorting algorithms run faster if the data are already partially sorted; other algorithms run slower in this case. A common way to avoid this problem is to analyze the worst case scenario. It is sometimes useful to analyze average case performance, but that’s usually harder, and it might not be obvious what set of cases to average over.
• Relative performance also depends on the size of the problem. A sorting algorithm that is fast for small lists might be slow for long lists. The usual solution to this problem is to express run time (or number of operations) as a function of problem size, and to compare the functions asymptotically as the problem size increases.

• 算法的相对性能可能取决于硬件特性，所以某个算法可能在机器 A 上更快，另一个在机器 B 上更快。这个问题的一般解法是规定一个机器模型，分析某个算法在给定模型下需要多少步（或多少次操作）。
• 相对性能可能取决于数据集的细节。例如，某些排序算法在数据已经部分有序时跑得更快，另一些则在此情况下更慢。避免这个问题常用的办法是分析最坏情形。有时分析平均情形性能也有用，但通常更难，而且该对哪些情形取平均并不显然。
• 相对性能还取决于问题规模。对短列表很快的排序算法，对长列表可能很慢。这个问题的通常解法是把运行时间（或操作次数）表示成问题规模的函数，并在问题规模增大时渐近地比较这些函数。

The good thing about this kind of comparison that it lends itself to simple classification of algorithms. For example, if I know that the run time of Algorithm A tends to be proportional to the size of the input, n, and Algorithm B tends to be proportional to n², then I expect A to be faster than B for large values of n.

This kind of analysis comes with some caveats, but we’ll get to that later.

B.1 Order of growth B.1 增长量级

Suppose you have analyzed two algorithms and expressed their run times in terms of the size of the input: Algorithm A takes 100n+1 steps to solve a problem with size n; Algorithm B takes n² + n + 1 steps.

The following table shows the run time of these algorithms for different problem sizes:

At n=10, Algorithm A looks pretty bad; it takes almost 10 times longer than Algorithm B. But for n=100 they are about the same, and for larger values A is much better.

The fundamental reason is that for large values of n, any function that contains an n² term will grow faster than a function whose leading term is n. The leading term is the term with the highest exponent.

For Algorithm A, the leading term has a large coefficient, 100, which is why B does better than A for small n. But regardless of the coefficients, there will always be some value of n where a n² > b n.

The same argument applies to the non-leading terms. Even if the run time of Algorithm A were n+1000000, it would still be better than Algorithm B for sufficiently large n.

In general, we expect an algorithm with a smaller leading term to be a better algorithm for large problems, but for smaller problems, there may be a crossover point where another algorithm is better. The location of the crossover point depends on the details of the algorithms, the inputs, and the hardware, so it is usually ignored for purposes of algorithmic analysis. But that doesn’t mean you can forget about it.

If two algorithms have the same leading order term, it is hard to say which is better; again, the answer depends on the details. So for algorithmic analysis, functions with the same leading term are considered equivalent, even if they have different coefficients.

An order of growth is a set of functions whose asymptotic growth behavior is considered equivalent. For example, 2n, 100n and n+1 belong to the same order of growth, which is written O(n) in Big-Oh notation and often called linear because every function in the set grows linearly with n.

All functions with the leading term n² belong to O(n²); they are quadratic, which is a fancy word for functions with the leading term n².

The following table shows some of the orders of growth that appear most commonly in algorithmic analysis, in increasing order of badness.

For the logarithmic terms, the base of the logarithm doesn’t matter; changing bases is the equivalent of multiplying by a constant, which doesn’t change the order of growth. Similarly, all exponential functions belong to the same order of growth regardless of the base of the exponent. Exponential functions grow very quickly, so exponential algorithms are only useful for small problems.

Exercise 1

Read the Wikipedia page on Big-Oh notation at http://en.wikipedia.org/wiki/Big_O_notation and answer the following questions:

1. What is the order of growth of n³ + n²? What about 1000000 n³ + n²? What about n³ + 1000000 n²?
2. What is the order of growth of (n² + n) · (n + 1)? Before you start multiplying, remember that you only need the leading term.
3. If f is in O(g), for some unspecified function g, what can we say about af+b?
4. If f₁ and f₂ are in O(g), what can we say about f₁ + f₂?
5. If f₁ is in O(g) and f₂ is in O(h), what can we say about f₁ + f₂?
6. If f₁ is in O(g) and f₂ is O(h), what can we say about f₁ · f₂?

1. n³ + n² 的增长量级是多少？1000000 n³ + n² 呢？n³ + 1000000 n² 呢？
2. (n² + n) · (n + 1) 的增长量级是多少？在你动手相乘之前，记住你只需要主项。
3. 如果 f 属于 O(g)（g 为某个未指定的函数），那么关于 af+b 我们能说什么？
4. 如果 f₁ 和 f₂ 都属于 O(g)，那么关于 f₁ + f₂ 我们能说什么？
5. 如果 f₁ 属于 O(g) 且 f₂ 属于 O(h)，那么关于 f₁ + f₂ 我们能说什么？
6. 如果 f₁ 属于 O(g) 且 f₂ 属于 O(h)，那么关于 f₁ · f₂ 我们能说什么？

Programmers who care about performance often find this kind of analysis hard to swallow. They have a point: sometimes the coefficients and the non-leading terms make a real difference. Sometimes the details of the hardware, the programming language, and the characteristics of the input make a big difference. And for small problems asymptotic behavior is irrelevant.

But if you keep those caveats in mind, algorithmic analysis is a useful tool. At least for large problems, the “better” algorithms is usually better, and sometimes it is much better. The difference between two algorithms with the same order of growth is usually a constant factor, but the difference between a good algorithm and a bad algorithm is unbounded!

B.2 Analysis of basic Python operations B.2 Python 基本操作的分析

Most arithmetic operations are constant time; multiplication usually takes longer than addition and subtraction, and division takes even longer, but these run times don’t depend on the magnitude of the operands. Very large integers are an exception; in that case the run time increases with the number of digits.

Indexing operations—reading or writing elements in a sequence or dictionary—are also constant time, regardless of the size of the data structure.

A for loop that traverses a sequence or dictionary is usually linear, as long as all of the operations in the body of the loop are constant time. For example, adding up the elements of a list is linear:

The built-in function for is also linear because it does the same thing, but it tends to be faster because it is a more efficient implementation; in the language of algorithmic analysis, it has a smaller leading coefficient.

If you use the same loop to “add” a list of strings, the run time is quadratic because string concatenation is linear.

The string method for0 is usually faster because it is linear in the total length of the strings.

As a rule of thumb, if the body of a loop is in O(n^a) then the whole loop is in O(n^a+1). The exception is if you can show that the loop exits after a constant number of iterations. If a loop runs k times regardless of n, then the loop is in O(n^a), even for large k.

Multiplying by k doesn’t change the order of growth, but neither does dividing. So if the body of a loop is in O(n^a) and it runs n/k times, the loop is in O(n^a+1), even for large k.

Most string and tuple operations are linear, except indexing and for, which are constant time. The built-in functions for and for are linear. The run-time of a slice operation is proportional to the length of the output, but independent of the size of the input.

All string methods are linear, but if the lengths of the strings are bounded by a constant—for example, operations on single characters—they are considered constant time.

Most list methods are linear, but there are some exceptions:

• Adding an element to the end of a list is constant time on average; when it runs out of room it occasionally gets copied to a bigger location, but the total time for n operations is O(n), so we say that the “amortized” time for one operation is O(1).
• Removing an element from the end of a list is constant time.
• Sorting is O(n logn).

• 往列表末尾追加一个元素，平均而言是常数时间；当空间不够时，它偶尔会被复制到更大的位置，但 n 次操作的总时间是 O(n)，所以我们说单次操作的「摊还」时间是 O(1)。
• 从列表末尾移除一个元素是常数时间。
• 排序是 O(n logn)。

Most dictionary operations and methods are constant time, but there are some exceptions:

• The run time of for0 is proportional to the number of elements, but not the size of the elements (it copies references, not the elements themselves).
• The run time of for000 is proportional to the size of the dictionary passed as a parameter, not the dictionary being updated.
• for0, for000 and for00 are linear because they return new lists; for00003, for000031 and for000032 are constant time because they return iterators. But if you loop through the iterators, the loop will be linear. Using the “iter” functions saves some overhead, but it doesn’t change the order of growth unless the number of items you access is bounded.

• for0 的运行时间与元素个数成正比，但与元素的大小无关（它复制的是引用，而不是元素本身）。
• for000 的运行时间与作为参数传入的字典的大小成正比，而不是与被更新的字典成正比。
• for0、for000 和 for00 是线性的，因为它们返回新列表；for00003、for000039 和 for000040 是常数时间，因为它们返回迭代器。但如果你循环遍历这些迭代器，循环就会是线性的。使用「iter」函数能节省一些开销，但除非你访问的元素个数有界，否则它不会改变增长量级。

The performance of dictionaries is one of the minor miracles of computer science. We will see how they work in Section B.4.

Exercise 2

Read the Wikipedia page on sorting algorithms at for000041



































and answer the following questions:

1. What is a “comparison sort?” What is the best worst-case order of growth for a comparison sort? What is the best worst-case order of growth for any sort algorithm?
2. What is the order of growth of bubble sort, and why does Barack Obama think it is “the wrong way to go?”
3. What is the order of growth of radix sort? What preconditions do we need to use it?
4. What is a stable sort and why might it matter in practice?
5. What is the worst sorting algorithm (that has a name)?
6. What sort algorithm does the C library use? What sort algorithm does Python use? Are these algorithms stable? You might have to Google around to find these answers.
7. Many of the non-comparison sorts are linear, so why does does Python use an O(n logn) comparison sort?

1. 什么是「比较排序」？比较排序在最坏情形下最好的增长量级是什么？任意排序算法在最坏情形下最好的增长量级是什么？
2. 冒泡排序的增长量级是什么，为什么 Barack Obama 认为它是「走错了方向」？
3. 基数排序的增长量级是什么？使用它需要哪些前提条件？
4. 什么是稳定排序，为什么在实践中它可能很重要？
5. 最差的（有名有姓的）排序算法是什么？
6. C 标准库使用什么排序算法？Python 使用什么排序算法？这些算法稳定吗？你可能需要上网搜一搜才能找到这些答案。
7. 许多非比较排序都是线性的，那么为什么 Python 用的是 O(n logn) 的比较排序？

B.3 Analysis of search algorithms B.3 搜索算法分析

A search is an algorithm that takes a collection and a target item and determines whether the target is in the collection, often returning the index of the target.

The simplest search algorithm is a “linear search,” which traverses the items of the collection in order, stopping if it finds the target. In the worst case it has to traverse the entire collection, so the run time is linear.

The in operator for sequences uses a linear search; so do string methods like for0 and for00.

If the elements of the sequence are in order, you can use a bisection search, which is O(logn). Bisection search is similar to the algorithm you probably use to look a word up in a dictionary (a real dictionary, not the data structure). Instead of starting at the beginning and checking each item in order, you start with the item in the middle and check whether the word you are looking for comes before or after. If it comes before, then you search the first half of the sequence. Otherwise you search the second half. Either way, you cut the number of remaining items in half.

If the sequence has 1,000,000 items, it will take about 20 steps to find the word or conclude that it’s not there. So that’s about 50,000 times faster than a linear search.

Exercise 3

Write a function called for000049 that takes a sorted list and a target value and returns the index of the value in the list, if it’s there, or for0 if it’s not.

Or you could read the documentation of the for000 module and use that!

Bisection search can be much faster than linear search, but it requires the sequence to be in order, which might require extra work.

There is another data structure, called a hashtable that is even faster—it can do a search in constant time—and it doesn’t require the items to be sorted. Python dictionaries are implemented using hashtables, which is why most dictionary operations, including the in operator, are constant time.

B.4 Hashtables B.4 散列表

To explain how hashtables work and why their performance is so good, I start with a simple implementation of a map and gradually improve it until it’s a hashtable.

I use Python to demonstrate these implementations, but in real life you wouldn’t write code like this in Python; you would just use a dictionary! So for the rest of this chapter, you have to imagine that dictionaries don’t exist and you want to implement a data structure that maps from keys to values. The operations you have to implement are:

for000057:

Add a new item that maps from key k to value k. With a Python dictionary, k, this operation is written for00006.

for000062
:

Look up and return the value that corresponds to key for000. With a Python dictionary, k, this operation is written for000065 or for000066


.

for000067：

新增一个从键 k 映射到值 k 的项。在 Python 字典 k 中，这个操作写作 for00007。

for000072
：

查找并返回与键 for000 对应的值。在 Python 字典 k 中，这个操作写作 for000075 或 for000076


。

For now, I assume that each key only appears once. The simplest implementation of this interface uses a list of tuples, where each tuple is a key-value pair.

for appends a key-value tuple to the list of items, which takes constant time.

for uses a for loop to search the list: if it finds the target key it returns the corresponding value; otherwise it raises a for00008. So for is linear.

An alternative is to keep the list sorted by key. Then for could use a bisection search, which is O(logn). But inserting a new item in the middle of a list is linear, so this might not be the best option. There are other data structures (for000089
































) that can implement for and for in log time, but that’s still not as good as constant time, so let’s move on.

One way to improve for000096 is to break the list of key-value pairs into smaller lists. Here’s an implementation called for000097, which is a list of 100 LinearMaps. As we’ll see in a second, the order of growth for for is still linear, but for000099 is a step on the path toward hashtables:

for00010 makes a list of k for000107s.

for00011 is used by for and for to figure out which map to put the new item in, or which map to search.

for00011 uses the built-in function for0, which takes almost any Python object and returns an integer. A limitation of this implementation is that it only works with hashable keys. Mutable types like lists and dictionaries are unhashable.

Hashable objects that are considered equal return the same hash value, but the converse is not necessarily true: two different objects can return the same hash value.

for00012 uses the modulus operator to wrap the hash values into the range from 0 to for000122



, so the result is a legal index into the list. Of course, this means that many different hash values will wrap onto the same index. But if the hash function spreads things out pretty evenly (which is what hash functions are designed to do), then we expect n/100 items per LinearMap.

Since the run time of for000125


is proportional to the number of items, we expect BetterMap to be about 100 times faster than LinearMap. The order of growth is still linear, but the leading coefficient is smaller. That’s nice, but still not as good as a hashtable.

Here (finally) is the crucial idea that makes hashtables fast: if you can keep the maximum length of the LinearMaps bounded, for000127


is constant time. All you have to do is keep track of the number of items and when the number of items per LinearMap exceeds a threshold, resize the hashtable by adding more LinearMaps.

Here is an implementation of a hashtable:

Each for0001 contains a for000131; for00013 starts with just 2 LinearMaps and initializes for, which keeps track of the number of items.

for just dispatches to for000139. The real work happens in for, which checks the number of items and the size of the for000141: if they are equal, the average number of items per LinearMap is 1, so it calls for000.

for000 make a new for000149, twice as big as the previous one, and then “rehashes” the items from the old map to the new.

Rehashing is necessary because changing the number of LinearMaps changes the denominator of the modulus operator in for00015. That means that some objects that used to wrap into the same LinearMap will get split up (which is what we wanted, right?).

Rehashing is linear, so for000 is linear, which might seem bad, since I promised that for would be constant time. But remember that we don’t have to resize every time, so for is usually constant time and only occasionally linear. The total amount of work to run for n times is proportional to n, so the average time of each for is constant time!

To see how this works, think about starting with an empty HashTable and adding a sequence of items. We start with 2 LinearMaps, so the first 2 adds are fast (no resizing required). Let’s say that they take one unit of work each. The next add requires a resize, so we have to rehash the first two items (let’s call that 2 more units of work) and then add the third item (one more unit). Adding the next item costs 1 unit, so the total so far is 6 units of work for 4 items.

The next for costs 5 units, but the next three are only one unit each, so the total is 14 units for the first 8 adds.

The next for costs 9 units, but then we can add 7 more before the next resize, so the total is 30 units for the first 16 adds.

After 32 adds, the total cost is 62 units, and I hope you are starting to see a pattern. After n adds, where n is a power of two, the total cost is 2n−2 units, so the average work per add is a little less than 2 units. When n is a power of two, that’s the best case; for other values of n the average work is a little higher, but that’s not important. The important thing is that it is O(1).

Figure B.1 shows how this works graphically. Each block represents a unit of work. The columns show the total work for each add in order from left to right: the first two for0 cost 1 units, the third costs 3 units, etc.

Figure B.1: The cost of a hashtable add.

图 B.1：散列表 add 操作的成本。（原书插图未收录）

The extra work of rehashing appears as a sequence of increasingly tall towers with increasing space between them. Now if you knock over the towers, amortizing the cost of resizing over all adds, you can see graphically that the total cost after n adds is 2n − 2.

An important feature of this algorithm is that when we resize the HashTable it grows geometrically; that is, we multiply the size by a constant. If you increase the size arithmetically—adding a fixed number each time—the average time per for is linear.

You can download my implementation of HashMap from for000172



















, but remember that there is no reason to use it; if you want a map, just use a Python dictionary.

1

But if you get a question like this in an interview, I think a better answer is, “The fastest way to sort a million integers is to use whatever sort function is provided by the language I’m using. Its performance is good enough for the vast majority of applications, but if it turned out that my application was too slow, I would use a profiler to see where the time was being spent. If it looked like a faster sort algorithm would have a significant effect on performance, then I would look around for a good implementation of radix sort.”

1

不过，如果你在面试中遇到这样的问题，我觉得更好的回答是：「对一百万个整数排序最快的办法，是使用我所用语言提供的任何排序函数。它的性能对绝大多数应用来说都足够好了；但如果事实证明我的应用太慢，我会用一个性能分析器看看时间花在了哪里。如果看起来用一个更快的排序算法会对性能有显著影响，那我才会去找一个优秀的基数排序实现。」