没有合适的资源?快使用搜索试试~ 我知道了~
首页Python算法2版:探索高效解决旅行商问题与路径优化
Python算法2版:探索高效解决旅行商问题与路径优化
需积分: 9 32 下载量 131 浏览量
更新于2023-05-28
2
收藏 4.78MB PDF 举报
"《Python算法第二版》是一本专门探讨算法设计与实现的IT专业书籍,针对计算机科学中的核心问题提供了深入讲解。书中以实际问题为例,如规划访问瑞典所有地点的最短路径,展示了编程解决这类复杂问题的挑战。尽管一个简单的程序在处理小规模问题时表现良好,但在面对海量数据如中国庞大的公路和铁路网络时,却显得力不从心,耗时极长,甚至可能需要长达85年的CPU时间。 书中章节涵盖了算法设计的基本原理,如介绍性章节探讨算法的基础概念,而后续章节则逐步深化,包括计数方法、归纳与递归、搜索与遍历、分治策略、贪心算法的分析、动态规划和记忆化技术,以及借助图论解决匹配、割点和流的问题。作者通过Edsger W. Dijkstra等人的工作,展示了如何通过精确的计算从A点到B点的最短路径。 此外,书中还特别提到了GPS软件和在线地图服务能够快速找到两个城市之间的最短路线,这与书中所涉及的算法复杂度形成了鲜明对比。这表明,对于大规模问题,高效算法和优化技术的应用至关重要,而现代技术如并行计算和高效的软件设计方法(如Pedal to the Metal部分提到的加速Python)使得复杂的算法能够在现实中迅速得到解决。 本书不仅提供理论知识,还附有大量问题和算法列表,以及对练习题的提示,帮助读者通过实践掌握算法技巧。《Python算法第二版》是一本旨在培养读者算法思维,提升编程技能,适应实际问题解决需求的实用教材。"
资源详情
资源推荐
CHAPTER 2 ■ THE BASICS
13
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
2
is in the set O(n
2
), or, in set
notation, n
2
∈ O(n
2
). We often simply say that n
2
is O(n
2
).
The fact that n
2
does not grow faster than itself is not particularly interesting. More useful, perhaps, is the fact that
neither 2.4n
2
+ 7 nor the linear function n does. That is, we have both
2.4n
2
+
7 ∈ O(n
2
)
and
n
∈
O(n
2
).
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
2
), 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
2
).
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
0
and a positive constant c such that
f(n)
³
cg(n)
for all n ³ n
0
. 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
0
and two positive constants c
1
and c
2
such that
c
1
g(n)
£
f(n) £ c
2
g(n)
for all n ³ n
0
. This means that f and g have the same asymptotic growth. For example, 3n
2
+ 2 is Q(n
2
), but we could just
as well write that n
2
is Q(3n
2
+ 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.
cn
2
T (n )
n
0
Figure 2-1. For values of n greater than n
0
, T(n) is less than cn
2
, so T(n) is O(n
2
)
www.it-ebooks.info
CHAPTER 2 ■ THE BASICS
14
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).
5
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.
7
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
2
) Quadratic Comparing n objects to each other (see Chapter 3).
Q(n
3
) 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
5
grows faster than n
4
, and 5
n
grows faster than 4
n
.
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.
6
Because of this division, any running time in O(n
k
), for any k > 0,
5
For the “Cubic” and “Polynomial” row, this holds only when k ³ 3.
6
Interestingly, once a problem is shown to have a polynomial solution, an efficient polynomial solution can quite often be
found as well.
7
I’m using lg rather than log here, but either one is fine.
www.it-ebooks.info
CHAPTER 2 ■ THE BASICS
15
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
2
+ n
3
+ 42) = Q(n
3
).
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
2
might technically be O(n
3
), we usually prefer the tighter limit, O(n
2
). 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
2
) + Q(n
3
) simply means f + g, for some (unknown) functions f and
g, where f is Q(n
2
) and g is Q(n
3
). 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)
www.it-ebooks.info
CHAPTER 2 ■ THE BASICS
16
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)):
8
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
2
). 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
3
), four give us Q(n
4
),
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
8
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).
www.it-ebooks.info
CHAPTER 2 ■ THE BASICS
17
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
2
). The y-loop is clearly Q(n). This means that the code block
inside the x-loop is Q(n + n
2
). 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
2
)) = Q(n
2
+ n
3
) = Q(n
3
), 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.
9
9
Spoiler: The complexity of this example is still Q(n
2
).
www.it-ebooks.info
剩余302页未读,继续阅读
凌风清羽
- 粉丝: 5
- 资源: 10
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功