算法概论：探索与实践

需积分: 9 91 浏览量更新于2024-07-27 收藏 1.95MB PDF 举报

"算法概论-Algorithm" 这本"算法概论"是加州伯克利大学的一本经典算法教材，与"算法导论"一起被认为是算法领域的两大权威教材。它涵盖了广泛且深入的算法知识，旨在帮助读者理解、分析和设计高效的算法。书中首先介绍了算法的基本概念，包括算法的重要性、历史背景以及大O记法，这些都是理解算法效率的基础。大O记法是描述算法运行时间增长速度的数学工具，对于评估算法性能至关重要。接下来，书中的"算法与数字"章节深入讨论了基本的算术运算、模运算和素数检测。这些内容在密码学和安全领域有着广泛应用，例如在加密技术中。此外，还提到了随机化算法，这是一种利用随机数来设计和分析算法的方法，能够解决一些传统算法难以处理的问题。 "分治算法"章节讲解了如何通过分解问题来解决复杂问题，如快速乘法、递归关系、归并排序、寻找中位数以及快速傅里叶变换等。这些算法在实际编程中非常常见，尤其是在数据处理和计算密集型任务中。 "图的分解"章节则转向了图论，探讨了为什么图是解决问题的强大工具，以及如何用深度优先搜索和广度优先搜索遍历图。深度优先搜索适用于探索图的深层次结构，而广度优先搜索则常用于找到两个节点之间的最短路径。此外，还介绍了强连通组件和基于边的长度计算。最后的"图中的路径"章节深入研究了图的路径问题，包括距离计算、最短路径算法如迪杰斯特拉算法，以及如何在存在负权边的情况下找到最短路径。这些内容在路由、网络优化和物流等领域有着实际应用。这本书全面地介绍了算法的基本思想、设计技巧和分析方法，是学习算法和数据结构的宝贵资源，适合计算机科学的学生和专业人士阅读。通过深入学习，读者可以提升解决问题的能力，更好地理解和解决复杂计算问题。

Figure 0.2 Which running time is better?

1 2 3 4 5 6 7 8 9 10

100

2n+20

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).

In the preceding example, f

= Θ(f

) and f

= Ω(f

Big-O notation lets us focus on the big picture. When faced with a complicated function

like 3n

+ 4n + 5, we just replace it with O(f(n)), where f(n) is as simple as possible. In this

particular example we’d use O(n

), because the quadratic portion of the sum dominates the

rest. Here are some commonsense rules that help simplify functions by omitting dominated

terms:

1. Multiplicative constants can be omitted: 14n

becomes n

2. n

dominates n

if a > b: for instance, n

dominates n.

3. Any exponential dominates any polynomial: 3

dominates n

(it even dominates 2

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?)

剩余317页未读，继续阅读

liucheng17

粉丝: 3
资源: 19

算法概论：探索与实践

算法概论（Algorithm）

算法概论（Algorithm）.rar

算法概论[Algorithms]

matlab源码求一元函数-Mathematical-modeling-algorithm-and-Application:数学建模算法与应用

Introduction-to-Algorithm:算法简介中代码的Pythonic实现

matlab穷举法代码-algorithm_note:我对zh_CN编写的算法的个人学习笔记

算法概论（英文版） <algorithm>

离散数学概论-课程概览

离散数学概论-谓词逻辑基础

Algorithms.算法概论中文版

最新资源