Python算法教程第二版：英文全攻略

需积分: 9 42 浏览量更新于2024-07-18 收藏 4.36MB PDF 举报

《Python算法教程第二版》是一本专为对算法感兴趣的读者精心编写的英文教材，由Allitebooks提供高清文字版PDF。该教程涵盖了Python编程语言与算法基础的深入讲解，旨在帮助读者掌握核心算法思想和技巧。书中的内容按照循序渐进的方式组织，分为多个章节： 1. **第一章**：**介绍** - 提供了对算法的概述，帮助读者理解算法在计算机科学中的重要性和作用，以及如何在Python环境中应用。 2. **第二章**：**基础知识** - 介绍了Python的基本语法、数据类型和控制结构，为后续的算法讨论奠定了坚实的基础。 3. **第三章**：**计数基础** - 讲解了基本的计数技巧和方法，如查找、统计等，通过实例演示如何在Python中实现这些操作。 4. **第四章**：**归纳与递归与简化** - 探讨了递归这一强大的算法设计工具，同时讲解了如何将复杂问题简化，通过递归或迭代来解决。 5. **第五章**：**遍历：算法的核心** - 学习如何通过遍历数据结构（如列表、树等）来执行算法，这是理解和实现许多算法的关键。 6. **第六章**：**分治策略** - 强调了将大问题分解为小问题并逐个解决的策略，如排序、搜索算法的实现。 7. **第七章**：**贪婪算法与证明** - 深入探讨了贪婪算法的原理和适用场景，并通过实例展示其有效性。 8. **第八章**：**复杂依赖与记忆化** - 讨论了处理有相互依赖关系的问题时如何运用记忆化技术优化算法性能。 9. **第九章**：**从A到B：Edsger W. Dijkstra和其他先驱** - 介绍了算法历史上的关键人物及其贡献，通过他们的工作学习算法的设计哲学。 10. **第十章**：**匹配、割集与流** - 进一步扩展到图论，探讨了匹配算法、最小割问题和最大流问题，这些都是网络优化中的核心概念。 11. **第十一章**：**硬问题与适度的宽松** - 探讨算法复杂度理论，以及如何在实际问题中权衡算法效率与复杂性。附录部分提供了额外的支持，如： - **附录A**：**从理论到实践：加速Python** - 着重于如何利用Python的高效库和工具提高算法实现的性能。 - **附录B**：**问题与算法列表** - 为读者提供了大量练习题和实际案例，以巩固所学知识。 - **附录C**：**图术语** - 对于理解图形算法至关重要，解释了图的各个组成部分和相关概念。 - **附录D**：**练习题提示** - 提供了解题思路和可能的解决方案，帮助读者解决书中习题。这本教程不仅适合初学者系统学习算法，也适合有一定基础的开发者深入理解算法在Python中的实现，提升编程技能。通过本书，读者将建立起坚实的算法基础，并能将其应用于实际项目中。

CHAPTER 2 ■ THE BASICS

This is a fairly straightforward and understandable definition, although it may seem a bit foreign at first. Basically,

O(g) is the set of functions that do not grow faster than g. For example, the function n

is in the set O(n

), or, in set

notation, n

∈ O(n

). We often simply say that n

is O(n

The fact that n

does not grow faster than itself is not particularly interesting. More useful, perhaps, is the fact that

neither 2.4n

+ 7 nor the linear function n does. That is, we have both

2.4n

7 ∈ O(n

)

and

∈

O(n

The first example shows us that we are now able to represent a function without all its bells and whistles; we can

drop the 2.4 and the 7 and simply express the function as O(n

), which gives us just the information we need. The

second shows us that O can be used to express loose limits as well: Any function that is better (that is, doesn’t grow

faster) than g can be found in O(g).

How does this relate to our original example? Well, the thing is, even though we can’t be sure of the details

(after all, they depend on both the Python version and the hardware you’re using), we can describe the operations

asymptotically: The running time of appending n numbers to a Python list is O(n), while inserting n numbers at its

beginning is O(n

The other two, W and Q, are just variations of O. W is its complete opposite: A function f is in W(g) if it satisfies the

following condition: There exists a natural number n

and a positive constant c such that

f(n)

cg(n)

for all n ³ n

. So, where O forms a so-called asymptotic upper bound, W forms an asymptotic lower bound.

Note ■ Our first two asymptotic operators, O and W, are each other’s inverses: If f is O(g), then g is W(f ). Exercise 2-3

asks you to show this.

The sets formed by Q are simply intersections of the other two, that is, Q(g) = O(g) ∩ W(g). In other words, a function f is

in Q(g) if it satisfies the following condition: There exists a natural number n

and two positive constants c

and c

such that

g(n)

f(n) £ c

g(n)

for all n ³ n

. This means that f and g have the same asymptotic growth. For example, 3n

+ 2 is Q(n

), but we could just

as well write that n

is Q(3n

+ 2). By supplying an upper bound and a lower bound at the same time, the Q operator is

the most informative of the three, and I will use it when possible.

T (n )

Figure 2-1. For values of n greater than n

, T(n) is less than cn

, so T(n) is O(n

)

CHAPTER 2 ■ THE BASICS

Rules of the Road

While the definitions of the asymptotic operators can be a bit tough to use directly, they actually lead to some of the

simplest math ever. You can drop all multiplicative and additive constants, as well as all other “small parts” of your

function, which simplifies things a lot.

As a first step in juggling these asymptotic expressions, let’s take a look at some typical asymptotic classes, or

orders. Table 2-1 lists some of these, along with their names and some typical algorithms with these asymptotic

running times, also sometimes called running-time complexities. (If your math is a little rusty, you could take a look at

the sidebar “A Quick Math Refresher” later in the chapter.) An important feature of this table is that the complexities

have been ordered so that each row dominates the previous one: If f is found higher in the table than g, then f is O(g).

Table 2-1. Common Examples of Asymptotic Running Times

Complexity Name Examples, Comments

Q(1) Constant Hash table lookup and modification (see “Black Box” sidebar on dict).

Q(lg n) Logarithmic Binary search (see Chapter 6). Logarithm base unimportant.

Q(n) Linear Iterating over a list.

Q(n lg n) Loglinear Optimal sorting of arbitrary values (see Chapter 6). Same as Q(lg n!).

Q(n

) Quadratic Comparing n objects to each other (see Chapter 3).

Q(n

) Cubic Floyd and Warshall’s algorithms (see Chapters 8 and 9).

O(nk) Polynomial k nested for loops over n (if k is a positive integer). For any constant k > 0.

W(kn) Exponential Producing every subset of n items (k = 2; see Chapter 3). Any k > 1.

Q(n!) Factorial Producing every ordering of n values.

Note ■ Actually, the relationship is even stricter: f is o(g), where the “Little Oh” is a stricter version if “Big Oh.”

Intuitively, instead of “doesn’t grow faster than,” it means “grows slower than.” Formally, it states that f(n)/g(n) converges

to zero as n grows to infinity. You don’t really need to worry about this, though.

Any polynomial (that is, with any power k > 0, even a fractional one) dominates any logarithm (that is, with any

base), and any exponential (with any base k > 1) dominates any polynomial (see Exercises 2-5 and 2-6). Actually, all

logarithms are asymptotically equivalent—they differ only by constant factors (see Exercise 2-4). Polynomials and

exponentials, however, have different asymptotic growth depending on their exponents or bases, respectively. So, n

grows faster than n

, and 5

grows faster than 4

The table primarily uses Q notation, but the terms polynomial and exponential are a bit special, because of

the role they play in separating tractable (“solvable”) problems from intractable (“unsolvable”) ones, as discussed

in Chapter 11. Basically, an algorithm with a polynomial running time is considered feasible, while an exponential

one is generally useless. Although this isn’t entirely true in practice, (Q(n

100

) is no more practically useful than

Q(2n)); it is, in many cases, a useful distinction.

Because of this division, any running time in O(n

), for any k > 0,

For the “Cubic” and “Polynomial” row, this holds only when k ³ 3.

Interestingly, once a problem is shown to have a polynomial solution, an efficient polynomial solution can quite often be

found as well.

I’m using lg rather than log here, but either one is fine.

CHAPTER 2 ■ THE BASICS

is called polynomial, even though the limit may not be tight. For example, even though binary search (explained in

the “Black Box” sidebar on bisect in Chapter 6) has a running time of Q(lg n), it is still said to be a polynomial-time

(or just polynomial) algorithm. Conversely, any running time in W(kn)—even one that is, say, Q(n!)—is said to be

exponential.

Now that we have an overview of some important orders of growth, we can formulate two simple rules:

In a sum, only the dominating summand matters.•

For example, Q(n

+ n

+ 42) = Q(n

In a product, constant factors don’t matter.•

For example, Q(4.2n lg n) = Q(n lg n).

In general, we try to keep the asymptotic expressions as simple as possible, eliminating as many unnecessary

parts as we can. For O and W, there is a third principle we usually follow:

Keep your upper or lower limits tight.•

In other words, we try to make the upper limits low and the lower limits high. For example,

although n

might technically be O(n

), we usually prefer the tighter limit, O(n

). In most cases,

though, the best thing is to simply use Q.

A practice that can make asymptotic expressions even more useful is that of using them instead of actual values,

in arithmetic expressions. Although this is technically incorrect (each asymptotic expression yields a set of functions,

after all), it is quite common. For example, Q(n

) + Q(n

) simply means f + g, for some (unknown) functions f and

g, where f is Q(n

) and g is Q(n

). Even though we cannot find the exact sum f + g, because we don’t know the exact

functions, we can find the asymptotic expression to cover it, as illustrated by the following two “bonus rules:”

• Q(f) + Q(g) = Q(f + g)

• Q(f) · Q(g) = Q(f · g)

Exercise 2-8 asks you to show that these are correct.

Taking the Asymptotics for a Spin

Let’s take a look at some simple programs and see whether we can determine their asymptotic running times. To

begin with, let’s consider programs where the (asymptotic) running time varies only with the problem size, not the

specifics of the instance in question. (The next section deals with what happens if the actual contents of the instances

matter to the running time.) This means, for example, that if statements are rather irrelevant for now. What’s

important is loops, in addition to straightforward code blocks. Function calls don’t really complicate things;

just calculate the complexity for the call and insert it at the right place.

Note ■ There is one situation where function calls can trip us up: when the function is recursive. This case is dealt with

in Chapters 3 and 4.

The loop-free case is simple: we are executing one statement before another, so their complexities are added.

Let’s say, for example, that we know that for a list of size n, a call to append is Q(1), while a call to insert at position 0 is

Q(n). Consider the following little two-line program fragment, where nums is a list of size n:

nums.append(1)

nums.insert(0,2)

CHAPTER 2 ■ THE BASICS

We know that the line first takes constant time. At the time we get to the second line, the list size has changed and

is now n + 1. This means that the complexity of the second line is Q(n + 1), which is the same as Q(n). Thus, the total

running time is the sum of the two complexities, Q(1) + Q(n) = Q(n).

Now, let’s consider some simple loops. Here’s a plain for loop over a sequence with n elements (numbers, say;

for example, seq = range(n)):

s = 0

for x in seq:

s += x

This is a straightforward implementation of what the sum function does: It iterates over seq and adds the elements

to the starting value in s. This performs a single constant-time operation (s += x) for each of the n elements of seq,

which means that its running time is linear, or Q(n). Note that the constant-time initialization (s = 0) is dominated by

the loop here.

The same logic applies to the “camouflaged” loops we find in list (or set or dict) comprehensions and generator

expressions, for example. The following list comprehension also has a linear running-time complexity:

squares = [x**2 for x in seq]

Several built-in functions and methods also have “hidden” loops in them. This generally applies to any function

or method that deals with every element of a container, such as sum or map, for example.

Things get a little bit (but not a lot) trickier when we start nesting loops. Let’s say we want to sum up all possible

products of the elements in seq; here’s an example:

s = 0

for x in seq:

for y in seq:

s += x*y

One thing worth noting about this implementation is that each product will be added twice. If 42 and 333 are

both in seq, for example, we’ll add both 42*333 and 333*42. That doesn’t really affect the running time; it’s just a

constant factor.

What’s the running time now? The basic rule is easy: The complexities of code blocks executed one after the

other are just added. The complexities of nested loops are multiplied. The reasoning is simple: For each round of the

outer loop, the inner one is executed in full. In this case, that means “linear times linear,” which is quadratic. In other

words, the running time is Q(n·n) = Q(n

). Actually, this multiplication rule means that for further levels of nesting,

we will just increment the power (that is, the exponent). Three nested linear loops give us Q(n

), four give us Q(n

and so forth.

The sequential and nested cases can be mixed, of course. Consider the following slight extension:

s = 0

for x in seq:

for y in seq:

s += x*y

for z in seq:

for w in seq:

s += x-w

If the elements are ints, the running time of each += is constant. However, Python also support big integers, or longs, which

automatically appear when your integers get big enough. This means you can break the constant-time assumption by using really

huge numbers. If you’re using floats, that won’t happen (but see the discussion of float problems near the end of the chapter).

CHAPTER 2 ■ THE BASICS

It may not be entirely clear what we’re computing here (I certainly have no idea), but we should still be able to

find the running time, using our rules. The z-loop is run for a linear number of iterations, and it contains a linear

loop, so the total complexity there is quadratic, or Q(n

). The y-loop is clearly Q(n). This means that the code block

inside the x-loop is Q(n + n

). This entire block is executed for each round of the x-loop, which is run n times. We

use our multiplication rule and get Q(n(n + n

)) = Q(n

+ n

) = Q(n

), that is, cubic. We could arrive at this conclusion

even more easily by noting that the y-loop is dominated by the z-loop and can be ignored, giving the inner block a

quadratic running time. “Quadratic times linear” gives us cubic.

The loops need not all be repeated Q(n) times, of course. Let’s say we have two sequences, seq1 and seq2, where

seq1 contains n elements and seq2 contains m elements. The following code will then have a running time of Q(nm).

s = 0

for x in seq1:

for y in seq2:

s += x*y

In fact, the inner loop need not even be executed the same number of times for each iteration of the outer loop.

This is where things can get a bit fiddly. Instead of just multiplying two iteration counts, such as n and m in the

previous example, we now have to sum the iteration counts of the inner loop. What that means should be clear in the

following example:

seq1 = [[0, 1], [2], [3, 4, 5]]

s = 0

for seq2 in seq1:

for x in seq2:

s += x

The statement s += x is now performed 2 + 1 + 3 = 6 times. The length of seq2 gives us the running time of the

inner loop, but because it varies, we cannot simply multiply it by the iteration count of the outer loop. A more realistic

example is the following, which revisits our original example—multiplying every combination of elements from a

sequence:

s = 0

n = len(seq)

for i in range(n-1):

for j in range(i+1, n):

s += seq[i] * seq[j]

To avoid multiplying objects with themselves or adding the same product twice, the outer loop now avoids the

last item, and the inner loop iterates over the items only after the one currently considered by the outer one. This is

actually a lot less confusing than it might seem, but finding the complexity here requires a little bit more care. This is

one of the important cases of counting that is covered in the next chapter.

Spoiler: The complexity of this example is still Q(n

www.allitebooks.com

剩余302页未读，继续阅读

weixin_41926302

粉丝: 0
资源: 1

Python算法教程第二版：英文全攻略

Python算法第二版：掌握基础算法与实战

《Python程序设计与算法基础教程（第二版）》第九章课后习题答案.pdf

Visual C++版计算机图形学原理与算法教程第二版学习资源

Python算法教程（第二版）英文版

Python算法教程英文版

免费 Python算法教程_中文版pdf

Python Algorithm 算法第二版

Python程序设计与算法基础教程（第二版）微课版第三章上机实践答案.pdf

算法导论第二版英文版

Python 基础教程 第三版

最新资源

Python 基础教程第三版