精通Python算法：基础算法指南

需积分: 50 135 浏览量更新于2024-07-21 收藏 2.7MB PDF 举报

“Python Algorithms”是一本深入讲解如何在Python语言中实现基础算法的书籍，被誉为Python版的“算法导论”。作者是Magnus Lie Hetland，这本书涵盖了数据结构和算法的核心概念，旨在帮助读者掌握Python编程中的算法应用。本书的主要内容可能包括但不限于以下几个方面： 1. **基础算法**：书中可能详细介绍了排序算法（如冒泡排序、快速排序、归并排序）、搜索算法（如线性搜索、二分查找）以及递归算法等基础知识，这些都是算法学习的基础。 2. **数据结构**：数据结构是算法的载体，书中可能会涵盖数组、链表、栈、队列、树（二叉树、平衡树如AVL和红黑树）、图等经典数据结构的定义、操作及Python实现。 3. **图论与网络流**：可能包含图的基本操作（如遍历、最短路径算法Dijkstra和Floyd-Warshall）、最小生成树算法（Prim和Kruskal）以及网络流问题的解决方法。 4. **动态规划**：这是一种解决复杂问题的有效策略，书中可能通过实例解释动态规划的思想和常见问题的求解过程。 5. **贪心算法与回溯法**：这两种算法在解决优化问题时非常有用，可能包括贪心选择性质的证明和回溯法在组合问题中的应用。 6. **复杂度分析**：介绍时间复杂度和空间复杂度的概念，帮助读者理解和评估算法的效率。 7. **递归与分治策略**：递归是解决问题的强大工具，而分治策略是很多高级算法的基础，书中可能会详细讲解这两个概念及其应用。 8. **随机化算法**：如蒙特卡洛方法和拉斯维加斯算法，这些在处理大规模数据或近似求解问题时非常有效。 9. **字符串处理**：Python在处理字符串方面有强大的功能，书中可能会介绍字符串匹配算法（如KMP和Boyer-Moore）等。 10. **实践应用**：通过实际案例展示如何在Python中应用这些算法，例如在数据分析、机器学习或Web开发中的应用。这本书对于想要提升Python编程能力，尤其是对算法和数据结构感兴趣的读者来说，是一份宝贵的资源。通过阅读和实践书中的内容，读者可以深入理解算法的本质，提高解决实际问题的能力。同时，由于Python语言的易读性和广泛应用，学习这方面的知识对于软件开发人员的职业发展具有重要意义。

■ INTRODUCTION

xvi

3UHIDFH

This book is a marriage of three of my passions: algorithms, Python programming, and explaining

things. To me, all three of these are about aesthetics—finding just the right way of doing something,

looking until you uncover a hint of elegance, and then polishing that until it shines. Or at least until it is a

bit shinier. Of course, when there’s a lot of material to cover, you may not get to polish things quite as

much as you want. Luckily, though, most of the contents in this book is prepolished, because I’m writing

about really beautiful algorithms and proofs, as well as one of the cutest programming languages out

there. As for the third part, I’ve tried hard to find explanations that will make things seem as obvious as

possible. Even so, I’m sure I have failed in many ways, and if you have suggestions for improving the

book, I’d be happy to hear from you. Who knows, maybe some of your ideas could make it into a future

edition? For now, though, I hope you have fun with what’s here and that you take any newfound insight

and run with it. If you can, use it to make the world a more awesome place, in whatever way seems right.

C H A P T E R 1

■ ■ ■

,QWURGXFWLRQ

1. Write down the problem.

2. Think real hard.

3. Write down the solution.

“The Feynman Algorithm”

as described by Murray Gell-Mann

Consider the following problem. You are to visit all the cities, towns, and villages of, say, Sweden and

then return to your starting point. This might take a while (there are 24 978 locations to visit, after all), so

you want to minimize your route. You plan on visiting each location exactly once, following the shortest

route possible. As a programmer, you certainly don’t want to plot the route by hand. Rather, you try to

write some code that will plan your trip for you. For some reason, however, you can’t seem to get it right.

A straightforward program works well for a smaller number of towns and cities but seems to run forever

on the actual problem, and improving the program turns out to be surprisingly hard. How come?

Actually, in 2004, a team of five researchers

found such a tour of Sweden, after a number of other

research teams had tried and failed. The five-man team used cutting-edge software with lots of clever

optimizations and tricks of the trade, running on a cluster of 96 Xeon 2.6 GHz workstations. Their

software ran from March 2003 until May 2004, before it finally printed out the optimal solution. Taking

various interruptions into account, the team estimated that the total CPU time spent was about 85 years!

Consider a similar problem: You want to get from Kashgar, in the westernmost regions of China, to

Ningbo, on the east coast, following the shortest route possible. Now, China has 3 583 715 km of

roadways and 77 834 km of railways, with millions of intersections to consider and a virtually

unfathomable number of possible routes to follow. It might seem that this problem is related to the

previous one, yet this shortest path problem is one solved routinely, with no appreciable delay, by GPS

software and online map services. If you give those two cities to your favorite map service, you should

get the shortest route in mere moments. What’s going on here?

You will learn more about both of these problems later in the book; the first one is called the

traveling salesman (or salesrep) problem and is covered in Chapter 11, while so-called shortest path

problems are primarily dealt with in Chapter 9. I also hope you will gain a rather deep insight into why

one problem seems like such a hard nut to crack while the other admits several well-known, efficient

solutions. More importantly, you will learn something about how to deal with algorithmic and

computational problems in general, either solving them efficiently, using one of the several techniques

and algorithms you encounter in this book, or showing that they are too hard and that approximate

solutions may be all you can hope for. This chapter briefly describes what the book is about—what you

David Applegate, Robert Bixby, Vašek Chvátal, William Cook, and Keld Helsgaun

CHAPTER 1 ■ INTRODUCTION

can expect and what is expected of you. It also outlines the specific contents of the various chapters to

come in case you want to skip around.

What’s All This, Then?

This is a book about algorithmic problem solving for Python programmers. Just like books on, say,

object-oriented patterns, the problems it deals with are of a general nature—as are the solutions. Your

task as an algorist will, in many cases, be more than simply to implement or execute an existing

algorithm, as you would, for example, in solving an algebra problem. Instead, you are expected to come

up with new algorithms—new general solutions to hitherto unseen, general problems. In this book, you

are going to learn principles for constructing such solutions.

This may not be your typical algorithm book, though. Most of the authoritative books on the subject

(such as the Knuth’s classics or the industry-standard textbook by Cormen et al.) have a heavy formal

and theoretical slant, even though some of them (such as the one by Kleinberg and Tardos) lean more in

the direction of readability. Instead of trying to replace any of these excellent books, I’d like to

supplement them. Building on my experience from teaching algorithms, I try to explain as clearly as

possible how the algorithms work and what common principles underlie many of them. For a

programmer, these explanations are probably enough. Chances are you’ll be able to understand why the

algorithms are correct and how to adapt them to new problems you may come to face. If, however, you

need the full depth of the more formalistic and encyclopedic textbooks, I hope the foundation you get in

this book will help you understand the theorems and proofs you encounter there.

There is another genre of algorithm books as well: the “(Data Structures and) Algorithms in blank”

kind, where the blank is the author’s favorite programming language. There are quite a few of these

(especially for blank = Java, it seems), but many of them focus on relatively basic data structures, to the

detriment of the more meaty stuff. This is understandable if the book is designed to be used in a basic

course on data structures, for example, but for a Python programmer, learning about singly and doubly

linked lists may not be all that exciting (although you will hear a bit about those in the next chapter). And

even though techniques such as hashing are highly important, you get hash tables for free in the form of

Python dictionaries; there’s no need to implement them from scratch. Instead, I focus on more high-

level algorithms. Many important concepts that are available as black-box implementations either in the

Python language itself or in the standard library (such as sorting, searching, and hashing) are explained

more briefly, in special “black box” sidebars throughout the text.

There is, of course, another factor that separates this book from those in the “Algorithms in

Java/C/C++/C#” genre, namely, that the blank is Python. This places the book one step closer to the

language-independent books (such as those by Knuth,

Cormen et al., and Kleinberg and Tardos, for

example), which often use pseudocode, the kind of fake programming language that is designed to be

readable rather than executable. One of Python’s distinguishing features is its readability; it is, more or

less, executable pseudocode. Even if you’ve never programmed in Python, you could probably decipher

the meaning of most basic Python programs. The code in this book is designed to be readable exactly in

this fashion—you need not be a Python expert to understand the examples (although you might need to

look up some built-in functions and the like). And if you want to pretend the examples are actually

pseudocode, feel free to do so. To sum up …

Knuth is also well-known for using assembly code for an abstract computer of his own design.

CHAPTER 1 ■ INTRODUCTION

What the book is about:

• Algorithm analysis, with a focus on asymptotic running time

• Basic principles of algorithm design

• How to represent well-known data structures in Python

• How to implement well-known algorithms in Python

What the book covers only briefly or partially:

• Algorithms that are directly available in Python, either as part of the language or

via the standard library

• Thorough and deep formalism (although the book has its share of proofs and

proof-like explanations)

What the book isn’t about:

• Numerical or number-theoretical algorithms (except for some floating-point hints

in Chapter 2)

• Parallel algorithms and multicore programming

As you can see, “implementing things in Python” is just part of the picture. The design principles and

theoretical foundations are included in the hope that they’ll help you design your own algorithms and

data structures.

Why Are You Here?

When working with algorithms, you’re trying to solve problems efficiently. Your programs should be fast;

the wait for a solution should be short. But what, exactly, do we mean by efficient, fast, and short? And

why would one care about these things in a language such as Python, which isn’t exactly lightning fast to

begin with? Why not rather switch to, say, C or Java?

First, Python is a lovely language, and you may not want to switch. Or maybe you have no choice in

the matter. But second, and perhaps most importantly, algorists don’t primarily worry about constant

differences in performance.

If one program takes twice, or even ten times, as long as another to finish, it

may still be fast enough, and the slower program (or language) may have other desirable properties, such

as being more readable. Tweaking and optimizing can be costly in many ways and is not a task to be

taken on lightly. What does matter, though, no matter the language, is how your program scales. If you

double the size of your input, what happens? Will your program run for twice as long? Four times? More?

Will the running time double even if you add just one measly bit to the input? These are the kind of

differences that will easily trump language or hardware choice, if your problems get big enough. And in

some cases “big enough” needn’t be all that big. Your main weapon in whittling down the growth of your

running time is—you guessed it—a solid understanding of algorithm design.

Let’s try a little experiment. Fire up an interactive Python interpreter, and enter the following:

Of course, the book is also not about a lot of other things ….

I’m talking about constant multiplicative factors here, such as doubling or halving the execution time.

CHAPTER 1 ■ INTRODUCTION

>>> count = 10**5

>>> nums = []

>>> for i in range(count):

... nums.append(i)

...

>>> nums.reverse()

Not the most useful piece of code, perhaps. It simply appends a bunch of numbers to an (initially)

empty list and then reverses that list. In a more realistic situation, the numbers might come from some

outside source (they could be incoming connections to a server, for example), and you want to add them

to your list in reverse order, perhaps to prioritize the most recent ones. Now you get an idea: instead of

reversing the list at the end, couldn’t you just insert the numbers at the beginning, as they appear?

Here’s an attempt to streamline the code (continuing in the same interpreter window):

>>> nums = []

>>> for i in range(count):

... nums.insert(0, i)

Unless you’ve encountered this situation before, the new code might look promising, but try to run

it. Chances are you’ll notice a distinct slowdown. On my computer, the second piece of code takes over

100 times as long as the first to finish. Not only is it slower, but it also scales worse with the problem size.

Try, for example, to increase count from 10**5 to 10**6. As expected, this increases the running time

for the first piece of code by a factor of about ten … but the second version is slowed by roughly two

orders of magnitude, making it more than a thousand times slower than the first! As you can probably

guess, the discrepancy between the two versions only increases as the problem gets bigger, making the

choice between them ever more crucial.

■ Note This is an example of linear vs. quadratic growth, a topic dealt with in detail in Chapter 3. The specific

issue underlying the quadratic growth is explained in the discussion of vectors (or dynamic arrays) in the black box

sidebar on

list

in Chapter 2.

Some Prerequisites

This book is intended for two groups of people: Python programmers, who want to beef up their

algorithmics, and students taking algorithm courses, who want a supplement to their plain-vanilla

algorithms textbook. Even if you belong to the latter group, I’m assuming you have a familiarity with

programming in general and with Python in particular. If you don’t, perhaps my book Beginning Python

(which covers Python versions up to 3.0) can help? The Python web site also has a lot of useful material,

and Python is a really easy language to learn. There is some math in the pages ahead, but you don’t have

to be a math prodigy to follow the text. We’ll be dealing with some simple sums and nifty concepts such

as polynomials, exponentials, and logarithms, but I’ll explain it all as we go along.

Before heading off into the mysterious and wondrous lands of computer science, you should have

your equipment ready. As a Python programmer, I assume you have your own favorite text/code editor

or integrated development environment—I’m not going to interfere with that. When it comes to Python

versions, the book is written to be reasonably version-independent, meaning that most of the code

should work with both the Python 2 and 3 series. Where backward-incompatible Python 3 features are

used, there will be explanations on how to implement the algorithm in Python 2 as well. (And if, for some

剩余324页未读，继续阅读

Lucosax-Yang

粉丝: 7
资源: 23

精通Python算法：基础算法指南

Python Algorithms, 2nd Edition

Python Algorithms, Mastering Basic Algorithms in the Python 2014

Python Algorithms Mastering Basic Algorithms in the Python Language.pdf.rar

python数据结构与算法练习书籍推荐

python算法数据结构书籍

python算法学习资料

python 算法实例和数据集

ann-benchmarks怎么安装使用

data structures and algorithms for python

data structures and algorithms in python

最新资源