Dasgupta, Papadimitriou, Vazirani算法专著2008版：理论与实践

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

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO

das23402

Ch00 GTBL020-Dasgupta-v10 August 2, 2006 2:44

Chapter 0 Algorithms

Figure 0.1 The proliferation of recursive calls in fib1.

n−3

n−1

n−4

n−2

n−4

n−6

n−5

n−4

n−2

n−3

n−4

n−5

As with fib1, the correctness of this algorithm is self-evident because it directly

uses the definition of F

. How long does it take? The inner loop consists of a single

computer step and is executed n − 1 times. Therefore the number of computer steps

used by fib2 is linear in n. From exponential we are down to polynomial, a huge

breakthrough in running time. It is now perfectly reasonable to compute F

200

even F

200,000

As we will see repeatedly throughout this book, the right algorithm makes all the

difference.

More careful analysis

In our discussion so far, we have been counting the number of basic computer steps

executed by each algorithm and thinking of these basic steps as taking a constant

amount of time. This is a very useful simplification. After all, a processor’s instruc-

tion set has a variety of basic primitives—branching, storing to memory, comparing

numbers, simple arithmetic, and so on—and rather than distinguishing between

these elementary operations, it is far more convenient to lump them together into

one category.

But looking back at our treatment of Fibonacci algorithms, we have been too liberal

with what we consider a basic step. It is reasonable to treat addition as a single

computer step if small numbers are being added, 32-bit numbers say. But the nth

Fibonacci number is about 0.694n bits long, and this can far exceed 32 as n grows.

To better appreciate the importance of this dichotomy between exponential and polynomial algorithms,

the reader may want to peek ahead to the story of Sissa and Moore in Chapter 8.

P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO

das23402

Ch00 GTBL020-Dasgupta-v10 August 2, 2006 2:44

6 0.3 Big-O notation

Arithmetic operations on arbitrarily large numbers cannot possibly be performed

in a single, constant-time step. We need to audit our earlier running time estimates

and make them more honest.

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly

proportional to n; this is not too hard to understand if you think back to the grade-

school procedure for addition, which works on one digit at a time. Thus fib1,

which performs about F

additions, actually uses a number of basic steps roughly

proportional to nF

. Likewise, the number of steps taken by fib2 is proportional

to n

, still polynomial in n and therefore exponentially superior to fib1. This cor-

rection to the running time analysis does not diminish our breakthrough.

But can we do even better than fib2? Indeed we can: see Exercise 0.4.

0.3 Big-O notation

We’ve just seen how sloppiness in the analysis of running times can lead to an

unacceptable level of inaccuracy in the result. But the opposite danger is also

present: it is possible to be too precise. An insightful analysis is based on the right

simplifications.

Expressing running time in terms of basic computer steps is already a simplifica-

tion. After all, the time taken by one such step depends crucially on the particu-

lar processor and even on details such as caching strategy (as a result of which

the running time can differ subtly from one execution to the next). Account-

ing for these architecture-specific minutiae is a nightmarishly complex task and

yields a result that does not generalize from one computer to the next. It there-

fore makes more sense to seek an uncluttered, machine-independent characteriza-

tion of an algorithm’s efficiency. To this end, we will always express running time

by counting the number of basic computer steps, as a function of the size of the

input.

And this simplification leads to another. Instead of reporting that an algorithm takes,

say, 5n

+ 4n + 3 steps on an input of size n, it is much simpler to leave out lower-

order terms such as 4n and 3 (which become insignificant as n grows), and even the

detail of the coefficient 5 in the leading term (computers will be five times faster in

a few years anyway), and just say that the algorithm takes time O(n

) (pronounced

“big oh of n

”).

It is time to define this notation precisely. In what follows, think of f (n) and g(n)

as the running times of two algorithms on inputs of size n.

Let f (n) and g(n) be functions from positive integers to positive reals. We say

f = O(g) (which means that “ f grows no faster than g”) if there is a constant

c > 0 such that f (n) ≤ c · g(n).

Saying f = O (g) is a very loose analog of “ f ≤ g.” It differs from the usual notion

of ≤ because of the constant c, so that for instance 10n = O(n). This constant also

allows us to disregard what happens for small values of n. For example, suppose we

剩余331页未读，继续阅读

craft-zhang

粉丝: 1
资源: 4

Dasgupta, Papadimitriou, Vazirani算法专著2008版：理论与实践

algorithm 头文件 说明

Algorithms(算法概论)pdf

algorithm by Dasgupta S., Papadimitriou C.H., Vazirani U.V.

algorithms,.s..dasgupta,.c.h..papadimitriou,.u.v..vazirani,.mgh,.2008

ModuleNotFoundError: No module named 'algorithms.train_LSTNet'

nx.algorithms.centrality是什么

报错：ModuleNotFoundError: No module named 'pymoo.algorithms.moo.sms'

ModuleNotFoundError: No module named 'torch.distributed.algorithms.join

module 'ray.rllib.algorithms.ppo' has no attribute 'DEFAULT_CONFIG'

拓扑排序专业参考文献

ModuleNotFoundError: No module named 'torch.distributed.algorithms.join'

AttributeError: module 'networkx.algorithms.community' has no attribute 'infomap'

ModuleNotFoundError: No module named 'pymoo.algorithms.moo.mopso'

cannot import name 'hamiltonian_path' from 'networkx.algorithms.approximation' (C:\Users\86182\anaconda3\lib\site-packages\networkx\algorithms\approximation\__init__.py)

module 'networkx.algorithms.approximation' has no attribute 'hamiltonian_path'

No module named 'pymoo.algorithms.nsga2'

def centrality(G): #计算度中心性,降序 dc = nx.algorithms.centrality.degree_centrality(G) return sorted(dc.items(), key=lambda x: x[1],reverse = True)啥意思

已知文本”The more the data, the better the performance of machine learning algorithms.”。统计文本中每个单词出现的次数

最新资源

algorithm 头文件说明

cannot import name 'hamiltonian_path' from 'networkx.algorithms.approximation' (C:\Users\86182\anaconda3\lib\site-packages\networkx\algorithms\approximation\init.py)