详解国外创新算法教程：从基础到高级

5星 · 超过95%的资源需积分: 9 32 浏览量更新于2024-07-26 收藏 1.97MB PDF 举报

"经典的算法教程"是一本深入讲解算法理论和实践应用的教材，由S.Dasgupta、C.H.Papadimitriou和U.V.Vazirani三位作者共同编著，于2006年出版。该教程具有创新性，适合对计算机科学特别是算法领域有一定基础的学习者阅读，内容涵盖了广泛的算法主题。在本书的开端，作者通过"Prologue"引导读者进入算法的世界，阐述了书籍与算法的关系，并用Fibonacci数列作为引入实例，展示了算法在实际问题中的应用。章节一"Algorithms with numbers"着重介绍了基础算术操作、模运算、素性检验、密码学和通用哈希函数等，这些是算法设计的基础，对于理解算法效率至关重要。随后的"Randomized algorithms: a virtual chapter"部分，介绍了随机算法，这是现代计算机科学的重要组成部分，它在解决某些问题时能提供高效的解决方案，如快速乘法、递归关系、归并排序、中位数计算、矩阵乘法以及快速傅里叶变换（FFT）等。第三部分是"Decomposition of graphs"，讲述了图论在算法中的应用，包括图的概念、深度优先搜索（DFS）在无向图和有向图中的区别、强连通分量的识别，以及这部分在路径查找、最短路径算法（如Dijkstra算法）中的作用。第四章"Paths in graphs"深入探讨了图中的路径分析，包括距离计算、广度优先搜索（BFS）、边的权重处理、Dijkstra算法及其优先队列实现，以及在存在负权边时的路径问题。这本书不仅涵盖了基本的算法规则和数据结构，还强调了算法分析中的Big-O表示法，帮助读者理解算法的时间复杂性和空间复杂性。每章末尾的大量练习题，旨在帮助读者巩固所学知识并提升解决问题的能力。通过学习这本经典的算法教程，读者将系统地掌握一系列核心算法技巧，并为后续的专业发展打下坚实基础。

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页未读，继续阅读

DQZQ

粉丝: 11

详解国外创新算法教程：从基础到高级

算法经典教程

经典的算法

经典算法演示

经典回溯算法教程

最经典的遗传算法教程

经典算法 mysql linux 视频教程

算法导论 经典书籍 教程

Python算法教程

遗传算法教程

PID算法教程

最新资源

算法导论经典书籍教程