精通Python算法：基础与实现

需积分: 17 97 浏览量更新于2024-07-27 2 收藏 2.56MB PDF 举报

"Python Algorithms - Mastering Basic Algorithms in the Python Language by Magnus Lie Hetland" 本书《Python Algorithms》是Magnus Lie Hetland的作品，旨在帮助读者掌握Python语言中的基础算法，并学习如何设计新的问题解决算法。作者通过深入浅出的方式，让读者能够理解和实现经典的计算机科学算法。在Python中，算法是解决问题和优化计算过程的关键工具。这本书将引导读者探索如何使用Python来实现这些算法，包括排序、搜索、图论、动态规划等多个领域。Python作为一种高级编程语言，以其简洁的语法和强大的库支持，成为学习算法的理想选择。书中可能会涵盖以下核心知识点： 1. **排序算法**：如冒泡排序、插入排序、选择排序、快速排序、归并排序以及堆排序等。每种排序算法的原理、实现和效率分析将被详细讨论。 2. **搜索算法**：包括线性搜索、二分搜索、广度优先搜索（BFS）和深度优先搜索（DFS）。这些搜索方法在数据结构如数组、链表和树中有着广泛应用。 3. **数据结构**：如栈、队列、堆、链表、树（二叉树、平衡树如AVL和红黑树）和图。理解这些数据结构及其操作对于有效实现和优化算法至关重要。 4. **图论**：涵盖图的基本概念，如邻接矩阵、邻接列表，以及Dijkstra算法、Floyd-Warshall算法和Prim算法等用于解决最短路径问题的方法。 5. **动态规划**：一种解决复杂问题的有效策略，通过将问题分解为子问题来求解。书中会讲解如何构建状态转移方程和记忆化搜索。 6. **递归与分治策略**：递归是许多算法的基础，如快速排序和归并排序。分治策略通过将大问题分解为小问题来解决，如归并排序和解决数位问题。 7. **复杂度分析**：了解时间复杂度和空间复杂度的概念，学会分析算法的运行效率，并根据这些分析优化算法。 8. **递推与回溯**：在解决组合优化问题和搜索问题时，递推和回溯是常用的技巧，如八皇后问题和迷宫问题的解决方案。 9. **随机化算法**：如鸽巢原理、鸽巢原则的应用，以及Monte Carlo方法，这些在处理大规模问题时非常有用。 10. **实用算法库**：介绍Python中的标准库如`heapq`、`bisect`和`collections`，以及第三方库如`networkx`和`scipy`，它们提供了现成的算法实现。通过阅读这本书，读者不仅可以学习到Python中的算法实现，还能培养解决问题的思维能力，这对于提升编程技能和解决实际问题具有极大价值。同时，书中实例丰富，有助于读者通过实践来巩固所学知识。

C H A P T E R 1

■ ■ ■

Introduction

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

CHAPTER 1 ■ INTRODUCTION

reason, you’re still stuck with, say, the Python 1.5 series, most of the code should still work, with a tweak

here and there.)

GETTING WHAT YOU NEED

In some operating systems, such as Mac OS X and several flavors of Linux, Python should already be

installed. If it is not, most Linux distributions will let you install the software you need through some form

of package manager. If you want or need to install Python manually, you can find all you need on the

Python web site,

http://python.org.

What’s in This Book

The book is structured as follows:

Chapter 1: Introduction. You’ve already gotten through most of this. It gives an overview of the book.

Chapter 2: The Basics. This covers the basic concepts and terminology, as well as some fundamental

math. Among other things, you learn how to be sloppier with your formulas than ever before, and still

get the right results, with asymptotic notation.

Chapter 3: Counting 101. More math—but it’s really fun math, I promise! There’s some basic

combinatorics for analyzing the running time of algorithms, as well as a gentle introduction to recursion

and recurrence relations.

Chapter 4: Induction and Recursion … and Reduction. The three terms in the title are crucial, and they

are closely related. Here we work with induction and recursion, which are virtually mirror images of each

other, both for designing new algorithms and for proving correctness. We also have a somewhat briefer

look at the idea of reduction, which runs as a common thread through almost all algorithmic work.

Chapter 5: Traversal: A Skeleton Key to Algorithmics. Traversal can be understood using the ideas of

induction and recursion, but it is in many ways a more concrete and specific technique. Several of the

algorithms in this book are simply augmented traversals, so mastering traversal will give you a real

jump start.

Chapter 6: Divide, Combine, and Conquer. When problems can be decomposed into independent

subproblems, you can recursively solve these subproblems and usually get efficient, correct algorithms

as a result. This principle has several applications, not all of which are entirely obvious, and it is a mental

tool well worth acquiring.

Chapter 7: Greed is Good? Prove It! Greedy algorithms are usually easy to construct. One can even

formulate a general scheme that most, if not all, greedy algorithms follow, yielding a plug-and-play

solution. Not only are they easy to construct, but they are usually very efficient. The problem is, it can be

hard to show that they are correct (and often they aren’t). This chapter deals with some well-known

examples and some more general methods for constructing correctness proofs.

Chapter 8: Tangled Dependencies and Memoization. This chapter is about the design method (or,

historically, the problem) called, somewhat confusingly, dynamic programming. It is an advanced

technique that can be hard to master but that also yields some of the most enduring insights and elegant

solutions in the field.

剩余323页未读，继续阅读

bugs2k

粉丝: 136
资源: 6

精通Python算法：基础与实现

Algorithm-Python-Algorithms.zip

Python algorithm

python算法库

python algorithms

Python Algorithms.Apress.2010_python_algorithms_

Python Algorithms源码

Python Algorithms - Mastering Basic Algorithms in the Python Language

Python Algorithms, Mastering Basic Algorithms in the Python 2014

Python Algorithms 2nd Edition

python Algorithms 2nd Edition

最新资源