算法入门与经典实例详解：从基础到高级

需积分: 18 129 浏览量更新于2024-07-22 收藏 1.95MB PDF 举报

本资源是一本名为《算法》的经典教材，由S.Dasgupta、C.H.Papadimitriou和U.V.Vazirani合著，于2006年出版。本书以其清晰易懂的语言，深入浅出地介绍了各种核心算法概念，适合初学者和专业人员学习。主要内容涵盖了以下几个部分： 1. **算法基础与数值操作**：章节1介绍了基本的算术运算，如加减乘除，以及模块运算（模数运算）的概念。同时，还讨论了 primality testing（素数检验）和 cryptography（密码学），展示了算法在信息安全中的应用。 2. **分治策略**：第二部分着重于算法设计中常见的分治方法，包括乘法的计算、递归关系的应用、merge sort（归并排序）算法，以及如何利用快速傅里叶变换（Fast Fourier Transform, FFT）优化效率。 3. **图论分解**：这部分探讨了为何研究图论及其在实际问题中的应用，如深度优先搜索（DFS）在无向图和有向图中的实现，强连通组件的识别，以及这些方法在图的结构分析中的作用。 4. **路径在图中的探索**：第四章涵盖了路径的计算，如计算两点之间的最短距离，breadth-first search（广度优先搜索，BFS）的介绍，以及Dijkstra's algorithm（迪杰斯特拉算法）用于寻找带权重图中的最短路径。这部分还涉及负权边处理和有向图的最短路径算法。 5. **贪心算法**：最后一部分介绍了贪心策略，这是一种常用的启发式算法，通过每一步局部最优的选择来达到全局最优或近似最优解，例如优先队列的不同实现和在最短路径问题中的应用。整个教材注重理论与实践相结合，通过实例和习题帮助读者掌握算法的核心思想和技巧。无论是初学者想要系统学习算法，还是希望提升现有技能的专业人士，这本书都是一个理想的资源。推荐下载并深入研读，以便更好地理解和应用这些算法原理。

Exercises

0.1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both (in which case

f = Θ(g)).

f(n) g(n)

(a) n −100 n −200

(b) n

1/2

2/3

(d) n log n 10n log 10n

(e) log 2n log 3n

(f) 10 log n log(n

)

(g) n

1.01

n log

(h) n

/ log n n(log n)

(i) n

0.1

(log n)

(j) (log n)

log n

n/ log n

(k)

√

n (log n)

(l) n

1/2

log

(m) n2

(n) 2

n+1

(o) n! 2

(p) (log n)

log n

(log

(q)

i=1

k+1

0.2. Show that, if c is a positive real number, then g(n) = 1 + c + c

+ ···+ c

is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.

) if c > 1.

The moral: in big-Θ terms, the sum of a geometric series is simply the ﬁrst term if the series is

strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the

series is unchanging.

0.3. The Fibonacci numbers F

, F

, . . . , are deﬁned by the rule

= 0, F

= 1, F

= F

n−1

+ F

n−2

In this problem we will conﬁrm that this sequence grows exponentially fast and obtain some

bounds on its growth.

(a) Use induction to prove that F

≥ 2

0.5n

for n ≥ 6.

(b) Find a constant c < 1 such that F

≤ 2

for all n ≥ 0. Show that your answer is correct.

= Ω(2

0.4. Is there a faster way to compute the nth Fibonacci number than by fib2 (page 11)? One idea

involves matrices.

We start by writing the equations F

= F

and F

= F

+ F

in matrix notation:







0 1

1 1







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

Bases and logs

Naturally, there is nothing special about the number 10—we just happen to have 10 ﬁngers,

and so 10 was an obvious place to pause and take counting to the next level. The Mayans

developed a similar positional system based on the number 20 (no shoes, see?). And of course

today computers represent numbers in binary.

How many digits are needed to represent the number N ≥ 0 in base b? Let’s see—with k

digits in base b we can express numbers up to b

−1; for instance, in decimal, three digits get

us all the way up to 999 = 10

− 1. By solving for k, we ﬁnd that dlog

(N + 1)e digits (about

log

N digits, give or take 1) are needed to write N in base b.

How much does the size of a number change when we change bases? Recall the rule for

converting logarithms from base a to base b: log

N = (log

N)/(log

b). So the size of integer

N in base a is the same as its size in base b, times a constant factor log

b. In big-O notation,

therefore, the base is irrelevant, and we write the size simply as O(log N). When we do not

specify a base, as we almost never will, we mean log

Incidentally, this function log N appears repeatedly in our subject, in many guises. Here’s

a sampling:

1. log N is, of course, the power to which you need to raise 2 in order to obtain N.

2. Going backward, it can also be seen as the number of times you must halve N to get

down to 1. (More precisely: dlog Ne.) This is useful when a number is halved at each

iteration of an algorithm, as in several examples later in the chapter.

3. It is the number of bits in the binary representation of N . (More precisely: dlog(N +1)e.)

4. It is also the depth of a complete binary tree with N nodes. (More precisely: blog Nc.)

5. It is even the sum 1 +

+ ··· +

, to within a constant factor (Exercise 1.5).

number, the carry is always a single digit, and so at any given step, three single-digit numbers

are added. Here’s an example showing the addition 53 + 35 in binary.

Carry: 1 1 1 1

1 1 0 1 0 1 (53)

1 0 0 0 1 1 (35)

1 0 1 1 0 0 0 (88)

Ordinarily we would spell out the algorithm in pseudocode, but in this case it is so familiar

that we do not repeat it. Instead we move straight to analyzing its efﬁciency.

Given two binary numbers x and y, how long does our algorithm take to add them? This

is the kind of question we shall persistently be asking throughout this book. We want the

answer expressed as a function of the size of the input: the number of bits of x and y, the

number of keystrokes needed to type them in.

Suppose x and y are each n bits long; in this chapter we will consistently use the letter n

for the sizes of numbers. Then the sum of x and y is n + 1 bits at most, and each individual bit

剩余313页未读，继续阅读

wbin91

粉丝: 0

算法入门与经典实例详解：从基础到高级

算法（第4版）.pdf

数据结构与算法.pdf

经典算法大全+共有51个例子.pdf

Matlab优化算法PDF

国密算法pdf文档及SM2算法JS实现

EM算法pdf讲义超详细

数据结构和算法PDF文档

积分方程的高精度算法pdf

MATLAB智能优化算法PDF及程序

遗传算法PDF+ppt+代码

最新资源