算法解锁：入门指南

需积分: 10 47 浏览量更新于2024-07-19 收藏 1.62MB PDF 举报

"算法开胃菜 - 入门算法导论" 本书《算法开胃菜》由Thomas H. Cormen撰写，旨在为读者提供一个轻松理解算法的入口，适合初学者和对算法感兴趣的读者。 MIT Press出版，这本书在2013年首次发行，并强调未经许可，任何部分不得以任何形式复制。算法是计算机科学的基础，它们是解决问题和执行任务的步骤序列。《算法开胃菜》将深入探讨这一主题，帮助读者理解算法的重要性。书中的内容不仅包括理论介绍，还可能涉及实际应用，使读者能够运用所学解决实际问题。书中可能会涵盖以下几个关键知识点： 1. **算法的基本概念**：定义什么是算法，它的组成部分，以及如何用伪代码或编程语言来表示算法。读者将了解到算法的五大特性：输入、输出、明确性、有限性、和可行性。 2. **排序与搜索算法**：这是最基础的算法类型，包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。此外，还会介绍线性搜索和二分查找等经典搜索算法。 3. **数据结构**：数据结构是存储和组织数据的方式，如数组、链表、栈、队列、树（二叉树、平衡树）和图。理解数据结构有助于优化算法性能。 4. **递归与分治策略**：递归是函数调用自身的过程，而分治策略则是将大问题分解为小问题来解决。这两个概念在算法设计中非常关键。 5. **动态规划**：这是一种优化技术，通过解决子问题并存储结果来避免重复计算，通常用于解决最优化问题。 6. **图算法**：如Dijkstra最短路径算法、Floyd-Warshall所有顶点间的最短路径、Prim最小生成树算法和Kruskal算法。 7. **复杂度分析**：理解时间复杂度和空间复杂度的概念，学习如何评估算法的效率，以便在实际应用中选择最适合的算法。 8. **问题解决技巧**：书中可能会教授如何分析问题，设计算法，以及如何调试和优化算法。 9. **算法设计模式**：介绍常见的算法设计模式，如贪心算法、回溯法和随机化算法。 10. **引用与索引**：书中提供的参考文献和索引将帮助读者深入研究特定主题或查找进一步的学习资料。通过《算法开胃菜》，读者不仅可以了解算法的基本原理，还能掌握实际操作技巧，为后续深入学习打下坚实基础。这本书对于希望提升计算机科学素养或准备面试的读者来说，无疑是一份宝贵的资源。

Chapter 1: What Are Algorithms and Why Should You Care? 3

rect? We won’t. In this book, we will focus on computer algorithms

that have knowable solutions.

Sometimes, however, we can accept that a computer algorithm might

produce an incorrect answer, as long as we can control how often

it does so. Encryption provides a good example. The commonly

used RSA cryptosystem relies on determining whether large num-

bers—really large, as in hundreds of digits long—are prime. If you

have ever written a computer program, you could probably write one

that determines whether a number n is prime. It would test all candidate

divisors from 2 through n  1, and if any of these candidates is indeed

a divisor of n,thenn is composite. If no number between 2 and n  1

is a divisor of n,thenn is prime. But if n is hundreds of digits long,

that’s a lot of candidate divisors, more than even a really fast computer

could check in any reasonable amount of time. Of course, you could

make some optimizations, such as eliminating all even candidates once

you ﬁnd that 2 is not a divisor, or stopping once you get to

n (since if

d is greater than

n and d is a divisor of n,thenn=d is less than

andisalsoadivisorofn; therefore, if n has a divisor, you will ﬁnd

it by the time you get to

n). If n is hundreds of digits long, then

although

n has only about half as many digits as n does, it’s still a

really large number. The good news is that we know of an algorithm

that tests quickly whether a number is prime. The bad news is that it

can make errors. In particular, if it declares that n is composite, then

n is deﬁnitely composite, but if it declares that n is prime, then there’s

a chance that n is actually composite. But the bad news is not all that

bad: we can control the error rate to be really low, such as one error in

every 2

times. That’s rare enough—one error in about every million

billion times—for most of us to be comfortable with using this method

to determine whether a number is prime for RSA.

Correctness is a tricky issue with another class of algorithms, called

approximation algorithms. Approximation algorithms apply to opti-

mization problems, in which we want to ﬁnd the best solution according

to some quantitative measure. Finding the fastest route, as a GPS does,

is one example, where the quantitative measure is travel time. For some

problems, we have no algorithm that ﬁnds an optimal solution in any

reasonable amount of time, but we know of an approximation algorithm

that, in a reasonable amount of time, can ﬁnd a solution that is almost

optimal. By “almost optimal,” we typically mean that the quantitative

measure of the solution found by the approximation algorithm is within

4 Chapter 1: What Are Algorithms and Why Should You Care?

some known factor of the optimal solution’s quantitative measure. As

long as we specify what the desired factor is, we can say that a correct

solution from an approximation algorithm is any solution that is within

that factor of the optimal solution.

Resource usage

What does it mean for an algorithm to use computational resources ef-

ﬁciently? We alluded to one measure of efﬁciency in the discussion

of approximation algorithms: time. An algorithm that gives a correct

solution but takes a long time to produce that correct solution might

be of little or no value. If your GPS took an hour to determine which

driving route it recommends, would you even bother to turn it on? In-

deed, time is the primary measure of efﬁciency that we use to evalu-

ate an algorithm, once we have shown that the algorithm gives a cor-

rect solution. But it is not the only measure. We might be concerned

with how much computer memory the algorithm requires (its “memory

footprint”), since an algorithm has to run within the available memory.

Other possible resources that an algorithm might use: network commu-

nication, random bits (because algorithms that make random choices

need a source of random numbers), or disk operations (for algorithms

that are designed to work with disk-resident data).

In this book, as in most of the algorithms literature, we will focus

on just one resource: time. How do we judge the time required by an

algorithm? Unlike correctness, which does not depend on the particular

computer that the algorithm runs on, the actual running time of an al-

gorithm depends on several factors extrinsic to the algorithm itself: the

speed of the computer, the programming language in which the algo-

rithm is implemented, the compiler or interpreter that translates the pro-

gram into code that runs on the computer, the skill of the programmer

who writes the program, and other activity taking place on the computer

concurrently with the running program. And that all assumes that the

algorithm runs on just one computer with all its data in memory.

If we were to evaluate the speed of an algorithm by implementing it in

a real programming language, running it on a particular computer with

a given input, and measuring the time the algorithm takes, we would

know nothing about how fast the algorithm ran on an input of a different

size, or possibly even on a different input of the same size. And if we

wanted to compare the relative speed of the algorithm with some other

algorithm for the same problem, we would have to implement them both

Chapter 1: What Are Algorithms and Why Should You Care? 5

and run both of them on various inputs of various sizes. How, then, can

we evaluate an algorithm’s speed?

The answer is that we do so by a combination of two ideas. First,

we determine how long the algorithm takes as a function of the size

of its input. In our route-ﬁnding example, the input would be some

representation of a roadmap, and its size would depend on the number

of intersections and the number of roads connecting intersections in the

map. (The physical size of the road network would not matter, since we

can characterize all distances by numbers and all numbers occupy the

same size in the input; the length of a road has no bearing on the input

size.) In a simpler example, searching a given list of items to determine

whether a particular item is present in the list, the size of the input would

be the number of items in the list.

Second, we focus on how fast the function that characterizes the run-

ning time grows with the input size—the rate of growth of the running

time. In Chapter 2, we’ll see the notations that we use to characterize

an algorithm’s running time, but what’s most interesting about our ap-

proach is that we look at only the dominant term in the running time,

and we don’t consider coefﬁcients. That is, we focus on the order of

growth of the running time. For example, suppose we could determine

that a speciﬁc implementation of a particular algorithm to search a list

of n items takes 50n C 125 machine cycles. The 50n term dominates

the 125 term once n gets large enough, starting at n  3 and increas-

ing in dominance for even larger list sizes. Thus, we don’t consider

the low-order term 125 when we describe the running time of this hy-

pothetical algorithm. What might surprise you is that we also drop the

coefﬁcient 50, thereby characterizing the running time as growing lin-

early with the input size n. As another example, if an algorithm took

20n

C 100n

C 300n C 200 machine cycles, we would say that its

running time grows as n

. Again, the low-order terms—100n

, 300n,

and 200—become less and less signiﬁcant as the input size n increases.

In practice, the coefﬁcients that we ignore do matter. But they de-

pend so heavily on the extrinsic factors that it’s entirely possible that if

we were comparing two algorithms, A and B, that have the same order

of growth and are run on the same input, then A might run faster than B

with a particular combination of machine, programming language, com-

piler/interpreter, and programmer, while B runs faster than A with some

other combination. Of course, if algorithms A and B both produce cor-

rect solutions and A always runs twice as fast as B, then, all other things

6 Chapter 1: What Are Algorithms and Why Should You Care?

being equal, we prefer to always run A instead of B. From the point of

view of comparing algorithms in the abstract, however, we focus on the

order of growth, unadorned by coefﬁcients or low-order terms.

The ﬁnal question that we ask in this chapter: “Why should I care about

computer algorithms?” The answer to this question depends on who

you are.

Computer algorithms for non-computer people

Even if you don’t consider yourself a computer insider, computer algo-

rithms matter to you. After all, unless you’re on a wilderness expedition

without a GPS, you probably use them every day. Did you search for

something on the Internet today? The search engine you used—whether

it was Google, Bing, or any other search engine—employed sophis-

ticated algorithms to search the Web and to decide in which order to

present its results. Did you drive your car today? Unless you’re driving

a classic vehicle, its on-board computers made millions of decisions, all

based on algorithms, during your trip. I could go on and on.

As an end user of algorithms, you owe it to yourself to learn a little bit

about how we design, characterize, and evaluate algorithms. I assume

that you have at least a mild interest, since you have picked up this book

and read this far. Good for you! Let’s see if we can get you up to speed

so that you can hold your own at your next cocktail party in which the

subject of algorithms comes up.

Computer algorithms for computer people

If you’re a computer person, then you had better care about computer

algorithms! Not only are they at the heart of, well, everything that goes

on inside your computer, but algorithms are just as much a technology

as everything else that goes on inside your computer. You can pay a

premium for a computer with the latest and greatest processor, but you

Yes, I realize that unless you live in Silicon Valley, the subject of algorithms rarely

comes up at cocktail parties that you attend, but for some reason, we computer science

professors think it important that our students not embarrass us at cocktail parties with

their lack of knowledge in particular areas of computer science.

Chapter 1: What Are Algorithms and Why Should You Care? 7

need to run implementations of good algorithms on that computer in

order for your money to be well spent.

Here’s an example that illustrates how algorithms are indeed a tech-

nology. In Chapter 3, we are going to see a few different algorithms

that sort a list of n values into ascending order. Some of these algo-

rithms will have running times that grow like n

, but some will have

running times that grow like only n lg n.Whatislgn? It is the base-2

logarithm of n,orlog

n. Computer scientists use base-2 logarithms

so frequently that just like mathematicians and scientists who use the

shorthand ln n for the natural logarithm—log

n—computer scientists

use their own shorthand for base-2 logarithms. Now, because the func-

tion lg n is the inverse of an exponential function, it grows very slowly

with n.Ifn D 2

,thenx D lg n. For example, 2

D 1024, and there-

fore lg 1024 is only 10; similarly 2

D 1,048,576 and so lg 1,048,576

is only 20;and2

D 1,073,741,824 means that lg 1,073,741,824 is

only 30. So a growth of n lg n vs. n

trades a factor of n for a factor of

only lg n, and that’s a deal you should take any day.

Let’s make this example more concrete by pitting a faster computer

(computer A) running a sorting algorithm whose running time on n val-

ues grows like n

against a slower computer (computer B) running a

sorting algorithm whose running time grows like n lg n. They each

must sort an array of 10 million numbers. (Although 10 million num-

bers might seem like a lot, if the numbers are eight-byte integers, then

the input occupies about 80 megabytes, which ﬁts in the memory of

even an inexpensive laptop computer many times over.) Suppose that

computer A executes 10 billion instructions per second (faster than any

single sequential computer at the time of this writing) and computer B

executes only 10 million instructions per second, so that computer A is

1000 times faster than computer B in raw computing power. To make

the difference even more dramatic, suppose that the world’s craftiest

programmer codes in machine language for computer A, and the result-

ing code requires 2n

instructions to sort n numbers. Suppose further

that just an average programmer writes for computer B, using a high-

level language with an inefﬁcient compiler, with the resulting code tak-

ing 50n lg n instructions. To sort 10 million numbers, computer A takes

2  .10

instructions

instructions/second

D 20,000 seconds ;

which is more than 5.5 hours, while computer B takes

剩余234页未读，继续阅读

santiagao

粉丝: 0
资源: 5

算法解锁：入门指南

算法基础.打开算法之门.[美]托马斯 H.科尔曼(带详细书签)

首次适应算法 最佳适应算法 循环首次适应算法

Java算法 + 数据挖掘算法

算法心得：高效算法的奥秘

基于Kmeans算法、MBSAS算法及DBSCAN算法的newsgroup18828文本聚类器

java算法大全源码包-java算法大全，有近100多种常见算法的源代码，是学习JAVA算法的难得资料

程序员算法大全

sift算法源码

遗传算法和BP人工神经网络算法C++实现代码

DBFLZO算法解压工具

最新资源

首次适应算法最佳适应算法循环首次适应算法　