数据结构与算法详解：复杂度分析与Java抽象

需积分: 10 181 浏览量更新于2024-07-21 收藏 1.47MB PDF 举报

本资源是一本名为《数据结构与算法》（DataStructures, Into Java）的教材，由Paul N. Hilfinger撰写，出版于加州大学伯克利分校。该书第七版主要探讨了计算机科学中的核心概念，特别是算法复杂性分析和数据类型在抽象中的应用。第一部分，"算法ic Complexity"，重点介绍了渐进复杂度分析和大O符号（Big-Oh notation）。作者通过实例来演示如何理解并衡量算法的时间效率，如线性搜索（Linear search），它的时间复杂度为O(n)，展示了算法在最坏、最好和平均情况下的运行速度。接着，作者提供了一个二次方程的例子，对比了它与线性搜索的增长速度，强调了爆炸性增长（如指数级或更高的复杂度）的概念。分治策略是另一个关键主题，如二分查找（Divide and conquer）和动态规划中的分而治之（Divide and fight to a standstill），这些策略有助于优化问题解决的效率。章节还讨论了平均时间复杂性的概念，即通过对最坏情况和最好情况的综合考虑，引入了“摊销”（amortization）的概念，以更全面地评估算法性能。此外，书中对问题的复杂度分类进行了深入解析，包括常数时间复杂度、线性、对数、平方等不同级别的复杂性。第二部分，“Data Types in the Abstract”，讲解了迭代器（Iterators）在数据结构中的作用，包括Iterator接口和ListIterator接口，它们提供了一种通用的方式来遍历集合类。然后，读者会学习到Java集合框架，这是一组抽象类和接口，如ArrayList、LinkedList和HashMap，它们封装了不同类型的数据结构，并支持高效的查询和操作。总体而言，这本书适合对计算机科学特别是数据结构和算法感兴趣的读者，旨在帮助他们掌握基本的理论知识和实践技巧，以便在设计高效程序时做出明智的选择。随着每章的深入，读者将能够理解和运用这些理论来优化代码执行效率，提升编程技能。版权信息表明，本书享有广泛的版权保护，且在2000年至2013年期间多次修订，确保内容的准确性和时效性。

16 CHAPTER 1. ALGORITHMIC COMPLEXITY

it. In other words,

boom

(0) = 0

boom

(i) = 2C

boom

(i − 1) + 1

A little m athematical massage:

boom

(M) = 2C

boom

(M − 1) + 1,

for M ≥ 1

= 2(2C

boom

(M − 2) + 1) + 1,

for M ≥ 2

= 2(···(2

{z }

·0 + 1) + 1) ··· + 1

{z }

0≤j≤M −1

= 2

− 1

and so C

boom

(M) ∈ Θ(2

1.3.4 Divide and conquer

Things become more interesting when the recursive calls decrease the size of pa-

rameters by a multiplicative rather than an additive factor. Consider, for example,

binary search.

/** Returns true iff X is one of

* A[L]...A[U]. Assumes A increasing,

* L>=0, U-L < A.length. */

static boolean isInB (int[] A, int L, int U, int X) {

if (L > U)

return false;

else {

int m = (L+U)/2;

if (A[m] == X)

return true;

else if (A[m] > X)

return isInB (A, L, m-1, X);

else

return isInB (A, m+1, U, X);

}

The worst-case time here depends on the number of elements of A under consid-

eration, U − L + 1, which we’ll call N. Let’s use the numb er of times the ﬁrst line

is executed as the cost, since if th e rest of the bod y is executed, the ﬁrst line also

had to have been executed

. If N > 1, the cost of executing isInB is 1 comparison

For those of you seeking arcane knowledge, we say that the test L>U dominates all other

statements.

1.4. AMORTIZATION 19

Increment: Flip the bits of the counter from right to left, up to and including the

ﬁrst 0-bit encountered (if any).

Clearly, if we are asked to give a worst-case bound on the cost of the increment

operation for an N-bit counter (in number of ﬂips), we’d have to say that it is

Θ(N): all the bits can be ﬂipped. Using just that bound, we’d then have to say

that the cost of performing M increment operations is Θ(M · N).

But the costs of consecutive increment operations are related. For example, if

one increment ﬂips more than one bit, the next increment will always ﬂip exactly

one (why?). In fact, if you consider the pattern of b it changes, you’ll see that the

units (rightmost) bit ﬂips on every increment, the 2’s bit on every second increment,

the 4’s bit on every fourth increment, and in general, then 2

’s bit on every (2

)

increment. Therefore, over any sequence of M consecutive increments, starting at

0, there will be

|{z}

unit’s ﬂips

+ ⌊M/2⌋

{z }

2’s ﬂips

+ ⌊M/4⌋

{z }

4’s ﬂips

+ . . . + ⌊M/2

⌋

{z }

’s ﬂips

, where n = ⌊lg M⌋

= 2

+ 2

n−1

+ 2

n−2

+ . . . + 1

{z }

n+1

−1

+(M − 2

)

= 2

− 1 + M

< 2M ﬂips

In other words, this is the same result we would get if we performed M incre-

ments each of which had a worst-case cost of 2 ﬂips, rather than N. We call 2 ﬂips

the amortized cost of an increment. To amortize in the context of algorithms is to

treat the cost of each individual operation in a sequence as if it were spread out

among all the operations in the sequence

. Any particular increment might take up

to N ﬂips, but we treat that as N/M ﬂips credited to each increment operation in

the sequence (and likewise count each increment that takes only one ﬂip as 1/M ﬂip

for each increment operation). The result is that we get a more realistic idea of how

much time the entire program will take; simply multiplying the ordinary worst-case

time by M gives us a very loose and pessimistic estimate. Nor is amortized cost the

same as average cost; it is a stronger measure. If a certain operation has a given

average cost, that leaves open the possibility that th ere is some unlikely sequence

of inputs that will make it look bad. A bound on amortized worst-case cost, on the

other hand, is guaranteed to hold regardless of input.

Another way to reach the same result uses what is called the potential method

.The

idea here is that we associate with our data structure (our bit sequence in this case)

a non-negative potential that represents work we wish to spr ead out over several op-

erations. If c

represents the actual cost of the i

operation on our data structure,

The word amortize comes from an Old French word meaning “to d eath.” The original meaning

from which the computer-science usage comes (introduced by Sleator and Tarjan), is “to gradually

write oﬀ the initial cost of something.”

Also due to D. Sleator.

20 CHAPTER 1. ALGORITHMIC COMPLEXITY

we deﬁne the amortized cost of the i

operation, a

so that

= c

+ Φ

i+1

− Φ

, (1.1)

where Φ

denotes the saved-up potential before the i

operation. That is, we give

ourselves the choice of in creasing Φ a little on any given operation and charging this

increase against a

, causing a

> c

when Φ increases. Alternatively, we can also

decrease a

below c

by having an operation reduce Φ, in eﬀect using up previously

saved increases. Assuming we start with Φ

= 0, the total cost of n operations is

0≤i<n

≤

0≤i<n

+ Φ

− Φ

+ 1)

= (

0≤i<n

) + Φ

− Φ

= (

0≤i<n

) − Φ

≤

0≤i<n

(1.2)

since we require that Φ

≥ 0. These a

therefore provid e conservative estimates of

the cumulative cost of the operations at each point.

For example, with our bit-ﬂipping example, we’ll d eﬁ ne Φ

as the total number

of 1-bits before the i

operation. The cost of the i

increment is always one plus

the number of 1-bits that ﬂip back to 0, which, because of how we’ve deﬁned it,

can never be more than Φ

(which of course is never negative). S o deﬁning a

= 2

for every operation satisﬁes Equation 1.1, again proving that we can bound th e

amortized cost of an increment by 2 bit-ﬂips.

I fudged a bit here by assu ming th at our bit counter always starts at 0. I f it

started instead at N

> 0, and we stopped after a single increment, then the total

cost (in bit ﬂips) could be as much as 1 + ⌊lg(N

+ 1)⌋. Since we want to insu re

that the inequality 1.2 holds for any n, we’ll have to do some adjusting to handle

this case. A simple trick is to redeﬁ ne Φ

= 0, keep other values of the Φ

the s ame

(the number of 1-bits before the i

operation, and ﬁnally deﬁne a

= c

+ Φ

. In

eﬀect, we charge a

with the start-up costs of our counting sequ en ce. Of cours e, this

means a

can be arbitrarily large, but that merely reﬂects reality; the remaining a

are still constant.

1.5 Complexity of Problems

So far, I have discussed only the analysis of an algorithm’s complexity. An algo-

rithm, however, is just a particular way of solving some problem. We might therefore

consider asking for complexity bounds on th e problem’s complexity. That is, can we

bound the complexity of the best possible algorithm? Obviously, if we have a partic-

ular algorithm and its time complexity is O(f(n)), where n is the size of the input,

then the complexity of the best possible algorithm must also be O(f(n)). We call

f(n), therefore, an upper bound on the (unknown) complexity of the best-possible

剩余250页未读，继续阅读

baidu_25451601

粉丝: 0
资源: 1

数据结构与算法详解：复杂度分析与Java抽象

Java数据结构和算法(第二版)+源代码+Applets

Java数据结构和算法.pdf

数据结构和算法分析 C++版 第三版

Java数据结构和算法

Java数据结构和算法详细笔记

Java数据结构和算法-第二版-高清扫描版-带目录书签

数据结构与算法分析习题答案

数据结构+算法综合资料库

《数据结构与算法分析》教学大纲详解：数据结构与算法基础

南邮数据结构教程：数据结构与算法解析

最新资源

数据结构和算法分析 C++版第三版