Dasgupta, Papadimitriou, Vazirani - 2006算法解析

需积分: 13 34 浏览量更新于2024-07-18 收藏 3.52MB PDF 举报

"Dasgupta, Papadimitriou, 和 Vazirani 合著的《Algorithms》是2006年由McGraw-Hill出版的一本关于算法的教科书，由加州大学圣地亚哥分校、伯克利分校的学者共同撰写。本书深入探讨了算法这一核心的计算机科学主题，旨在教授读者如何设计和分析算法。" 在计算机科学领域，算法是解决问题和执行任务的基础。这本书《Algorithms》由Sanjoy Dasgupta、Christos Papadimitriou和Umesh Vazirani三位知名学者共同编著，他们分别来自加州大学圣地亚哥分校和伯克利分校，具有深厚的学术背景和教学经验。书中涵盖了算法设计与分析的各个方面，包括但不限于排序、搜索、图论、动态规划、贪心算法、随机化算法以及近似算法等。排序算法是书中可能涉及的基础内容之一，如快速排序、归并排序、堆排序等，这些算法在实际应用中有着广泛的需求。搜索算法则包括深度优先搜索（DFS）、广度优先搜索（BFS）以及A*搜索等，它们在解决路径寻找、网络爬虫等问题时发挥着重要作用。图论算法是另一个重点，例如最小生成树算法（如Prim算法和Kruskal算法）、最短路径算法（Dijkstra算法和Floyd-Warshall算法）等，这些对于理解复杂网络和优化问题至关重要。动态规划和贪心算法则用于解决那些可以通过逐步决策过程来求解的问题，如背包问题、最长公共子序列问题等。随机化算法是现代计算中的一个重要分支，如鸽巢原理、Monte Carlo方法和Las Vegas算法，它们在处理大规模数据和解决NP难问题时展现出优势。近似算法则针对那些在有限时间内无法找到精确解的问题，提供可接受的近似解决方案。此外，本书还可能讨论了算法的时间复杂度和空间复杂度分析，这是评估算法效率的关键工具。通过这些分析，开发者能够选择最合适的算法以提高程序性能。《Algorithms》这本书旨在帮助读者掌握算法设计的核心原则和分析技术，从而具备解决复杂问题的能力，适合计算机科学专业的学生和研究人员阅读。其深入浅出的讲解方式和丰富的实例将有助于读者理解和应用这些重要的算法知识。

P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO

das23402

Ch00 GTBL020-Dasgupta-v10 August 2, 2006 2:44

Chapter 0 Algorithms 5

Figure 0.1 The proliferation of recursive calls in fib1.

n−3

n−1

n−4

n−2

n−4

n−6

n−5

n−4

n−2

n−3

n−4

n−5

As with fib1, the correctness of this algorithm is self-evident because it directly

uses the definition of F

. How long does it take? The inner loop consists of a single

computer step and is executed n − 1 times. Therefore the number of computer steps

used by fib2 is linear in n. From exponential we are down to polynomial, a huge

breakthrough in running time. It is now perfectly reasonable to compute F

200

even F

200,000

As we will see repeatedly throughout this book, the right algorithm makes all the

difference.

More careful analysis

In our discussion so far, we have been counting the number of basic computer steps

executed by each algorithm and thinking of these basic steps as taking a constant

amount of time. This is a very useful simplification. After all, a processor’s instruc-

tion set has a variety of basic primitives—branching, storing to memory, comparing

numbers, simple arithmetic, and so on—and rather than distinguishing between

these elementary operations, it is far more convenient to lump them together into

one category.

But looking back at our treatment of Fibonacci algorithms, we have been too liberal

with what we consider a basic step. It is reasonable to treat addition as a single

computer step if small numbers are being added, 32-bit numbers say. But the nth

Fibonacci number is about 0.694n bits long, and this can far exceed 32 as n grows.

To better appreciate the importance of this dichotomy between exponential and polynomial algorithms,

the reader may want to peek ahead to the story of Sissa and Moore in Chapter 8.

P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO

das23402

Ch00 GTBL020-Dasgupta-v10 August 2, 2006 2:44

6 0.3 Big-O notation

Arithmetic operations on arbitrarily large numbers cannot possibly be performed

in a single, constant-time step. We need to audit our earlier running time estimates

and make them more honest.

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly

proportional to n; this is not too hard to understand if you think back to the grade-

school procedure for addition, which works on one digit at a time. Thus fib1,

which performs about F

additions, actually uses a number of basic steps roughly

proportional to nF

. Likewise, the number of steps taken by fib2 is proportional

to n

, still polynomial in n and therefore exponentially superior to fib1. This cor-

rection to the running time analysis does not diminish our breakthrough.

But can we do even better than fib2? Indeed we can: see Exercise 0.4.

0.3 Big-O notation

We’ve just seen how sloppiness in the analysis of running times can lead to an

unacceptable level of inaccuracy in the result. But the opposite danger is also

present: it is possible to be too precise. An insightful analysis is based on the right

simplifications.

Expressing running time in terms of basic computer steps is already a simplifica-

tion. After all, the time taken by one such step depends crucially on the particu-

lar processor and even on details such as caching strategy (as a result of which

the running time can differ subtly from one execution to the next). Account-

ing for these architecture-specific minutiae is a nightmarishly complex task and

yields a result that does not generalize from one computer to the next. It there-

fore makes more sense to seek an uncluttered, machine-independent characteriza-

tion of an algorithm’s efficiency. To this end, we will always express running time

by counting the number of basic computer steps, as a function of the size of the

input.

And this simplification leads to another. Instead of reporting that an algorithm takes,

say, 5n

+ 4n + 3 steps on an input of size n, it is much simpler to leave out lower-

order terms such as 4n and 3 (which become insignificant as n grows), and even the

detail of the coefficient 5 in the leading term (computers will be five times faster in

a few years anyway), and just say that the algorithm takes time O(n

) (pronounced

“big oh of n

”).

It is time to define this notation precisely. In what follows, think of f (n) and g(n)

as the running times of two algorithms on inputs of size n.

Let f (n) and g(n) be functions from positive integers to positive reals. We say

f = O(g) (which means that “ f grows no faster than g”) if there is a constant

c > 0 such that f (n) ≤ c · g(n).

Saying f = O (g) is a very loose analog of “ f ≤ g.” It differs from the usual notion

of ≤ because of the constant c, so that for instance 10n = O(n). This constant also

allows us to disregard what happens for small values of n. For example, suppose we

剩余331页未读，继续阅读

weixin_43651694

粉丝: 1
资源: 5

Dasgupta, Papadimitriou, Vazirani - 2006算法解析

Algorithms:几种语言的一些算法

《Algorithms》部分答案

algorithms pdf

algorithms

algorithms.rar_algorithms

Algorithms_algorithms4_算法第四版_algorithms_

Computer Algorithms

Clever Algorithms

Bioinformatics Algorithms

python algorithms

最新资源