算法精粹：从图论到线性规划

需积分: 0 164 浏览量更新于2024-08-02 收藏 1.97MB PDF 举报

《算法》是一本由S.Dasgupta、C.H.Papadimitriou和U.V.Vazirani共同编著的权威计算机科学教材，版权于2006年。本书以深入浅出的方式探讨了算法设计与分析的基本概念，特别强调了在实际问题中的应用。全书分为多个章节，涵盖了广泛的算法主题。 **第0章：序言** 本章介绍了书籍与算法的关系，以及作者邀请读者通过 Fibonacci 数列的故事来理解算法的重要性。同时，作者还引入了 Big-O notation（大O符号），这是一种用于描述算法效率的工具，它表示算法运行时间与输入规模之间的关系。 **第1章：算法基础** 本章着重讲解算法设计，包括基本的算法描述方法和技巧。章节内容可能包括数组和列表操作，以及如何利用这些数据结构设计高效算法。 **第4章：图论算法** 这部分深入讨论了路径搜索和最短路径算法，如计算距离、广度优先搜索（BFS）、Dijkstra算法（用于寻找带权重的图中两点间的最短路径）等。此外，还涉及了优先队列实现及处理负权边的策略，以及在有向无环图（DAG）中的最短路径。 **第5章：贪心算法** 这一章展示了如何运用贪心策略解决优化问题，如最小生成树（如Prim或Kruskal算法）、Huffman编码（一种压缩数据的算法）以及解决某些逻辑难题，如Horn公式和集合覆盖问题。 **第6章：动态规划** 动态规划是解决问题的一种递归思想，本章通过实例如重新审视DAG中的最短路径、最长递增子序列、编辑距离、背包问题、矩阵链乘法等，展示了动态规划的强大作用。 **第7章：线性规划与约简** 本章转向更高级的主题，介绍了线性规划，其核心是求解目标函数在一组线性约束下的最优解。内容涵盖网络流、二分匹配问题、对偶理论以及零-一整数规划等内容，这些都是解决复杂优化问题的重要工具。《算法》这本书旨在帮助读者掌握算法设计的核心理念和实用技巧，无论是在理论研究还是实际工程中，都能为理解和解决各种计算机科学问题提供坚实的基础。随着每章内容的深入，读者不仅能够理解算法背后的原理，还能学会如何在实际问题中灵活运用它们，提升编程和解决问题的能力。

Algorithms

Figure 0.2 Which running time is better?

1 2 3 4 5 6 7 8 9 10

100

2n+20

disregard what happens for small values of n. For example, suppose we are choosing between

two algorithms for a particular computational task. One takes f

(n) = n

steps, while the

other takes f

(n) = 2n + 20 steps (Figure 0.2). Which is better? Well, this depends on the

value of n. For n ≤ 5, f

is smaller; thereafter, f

is the clear winner. In this case, f

scales

much better as n grows, and therefore it is superior.

This superiority is captured by the big-O notation: f

= O(f

), because

(n)

2n + 20

≤ 22

for all n; on the other hand, f

6= O(f

), since the ratio f

(n)/f

(n) = n

/(2n + 20) can get

arbitrarily large, and so no constant c will make the deﬁnition work.

Now another algorithm comes along, one that uses f

(n) = n + 1 steps. Is this better

than f

? Certainly, but only by a constant factor. The discrepancy between f

and f

is tiny

compared to the huge gap between f

and f

. In order to stay focused on the big picture, we

treat functions as equivalent if they differ only by multiplicative constants.

Returning to the deﬁnition of big-O, we see that f

= O(f

(n)

2n + 20

n + 1

≤ 20,

and of course f

= O(f

), this time with c = 1.

Just as O(·) is an analog of ≤, we can also deﬁne analogs of ≥ and = as follows:

f = Ω(g) means g = O(f)

f = Θ(g) means f = O(g) and f = Ω(g).

S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Similarly,







0 1

1 1









0 1

1 1







and in general



n+1





0 1

1 1







So, in order to compute F

, it sufﬁces to raise this 2 × 2 matrix, call it X, to the nth power.

(a) Show that two 2 × 2 matrices can be multiplied using 4 additions and 8 multiplications.

But how many matrix multiplications does it take to compute X

(b) Show that O(log n) matrix multiplications sufﬁce for computing X

. (Hint: Think about

computing X

Thus the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is

just O(log n), as compared to O(n) for fib2. Have we broken another exponential barrier?

The catch is that our new algorithm involves multiplication, not just addition; and multiplica-

tions of large numbers are slower than additions. We have already seen that, when the complex-

ity of arithmetic operations is taken into account, the running time of fib2 becomes O(n

(d) Let M(n) be the running time of an algorithm for multiplying n-bit numbers, and assume

that M(n) = O(n

) (the school method for multiplication, recalled in Chapter 1, achieves

this). Prove that the running time of fib3 is O(M(n) log n).

(e) Can you prove that the running time of fib3 is O(M(n))? (Hint: The lengths of the num-

bers being multiplied get doubled with every squaring.)

In conclusion, whether fib3 is faster than fib2 depends on whether we can multiply n-bit

integers faster than O(n

). Do you think this is possible? (The answer is in Chapter 2.)

Finally, there is a formula for the Fibonacci numbers:

√

1 +

√

−

√

1 −

√

So, it would appear that we only need to raise a couple of numbers to the nth power in order to

compute F

. The problem is that these numbers are irrational, and computing them to sufﬁcient

accuracy is nontrivial. In fact, our matrix method fib3 can be seen as a roundabout way of

raising these irrational numbers to the nth power. If you know your linear algebra, you should

see why. (Hint: What are the eigenvalues of the matrix X?)

剩余335页未读，继续阅读

dancer_robin

粉丝: 0
资源: 1

算法精粹：从图论到线性规划

Introduction to Algorithms Third Edition

Algorithms: Design and Analysis

Rigid Body Dynamics Algorithms Featherstone, Roy

algorithms

algorithms.rar_algorithms

Algorithms_algorithms4_算法第四版_algorithms_

Graph Algorithms

Computer Algorithms

python algorithms

algorithms app

最新资源