Java数据结构与算法分析

需积分: 9 160 浏览量更新于2024-08-01 收藏 1.46MB PDF 举报

"data-structures-Java.pdf" 这篇文档是关于数据结构与算法在Java中的应用，主要摘自"CS61BReader#2 Data Structures (Into Java)"的第五版，作者Paul N. Hilfinger，来自加州大学伯克利分校。这份材料对多个审阅者表示了感谢，他们帮助发现了早期版本中的错误。文档内容涵盖了算法复杂性分析、数据类型以及Java中的抽象集合等核心概念。 1. 算法复杂性 - 渐进复杂度分析和阶乘记法: 阐述了如何通过大O记法来分析算法的时间复杂性和空间复杂性，这是评估算法效率的关键方法。 - 示例分析: 提供了不同类型的算法示例，如线性搜索、二次方程等，用于演示大O记法的应用。 - 算法分析应用: 包括线性搜索、二次方例子例、指数增长的案例，以及分治法，展示了复杂度分析在实际问题中的应用。 - 分治策略: 介绍了如何利用分治法解决问题，并给出了一个相关例子。 - 平均化成本分析（Amortization）: 讨论了如何在处理一系列操作时平衡成本，使得单次操作的成本看起来更均匀。 - 问题的复杂性: 讨论了问题本身的复杂性，不仅仅是算法的复杂性，强调了问题规模对解决方案选择的影响。 - 对数性质: 介绍了一些关于对数的重要属性，这些属性经常在计算复杂性中发挥作用。 - 记号注释: 对用于表示算法复杂性的数学记号进行了说明，确保读者理解其含义。 2. 数据类型在抽象中 - 迭代器: 强调了在Java中遍历集合的重要工具——迭代器接口及其子接口ListIterator，它们允许双向遍历。 - Java集合抽象: 介绍了Java中的集合框架，包括Collection接口和Set接口，这些都是Java中处理数据结构的核心组件。 - Collection接口: 作为所有集合类的父接口，定义了添加、删除和查询元素的基本操作。 - Set接口: 代表不允许重复元素的集合，提供了独特的存储模型。这份资料详细解释了Java编程中数据结构和算法的基础知识，对于理解如何高效地组织和操作数据，以及如何设计和分析算法具有极大的价值。通过深入学习，读者可以提高编程能力，尤其是在处理大规模数据时，能够选择合适的数据结构和算法，从而优化程序性能。

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 number of times the ﬁrst line

is executed as the cost, since if the rest of the body is executed, the ﬁrst line also

had to have been executed

. If N > 1, th e 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 bit changes, you’ll see that the

units (rightmost) b it ﬂ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 sequ en ce of M consecutive increments, starting at

0, th ere 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 op eration 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 lo ose 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 there is some unlikely sequence

of inputs that will make it look b ad. 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 spread 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 death.” The original meaning

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

write oﬀ t he 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 increasing Φ 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 provide conservative estimates of

the cumulative cost of the operations at each point.

For example, with our bit-ﬂipping example, we’ll deﬁ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). So deﬁning a

= 2

for every operation satisﬁes Equation 1.1, again pr oving that we can bound the

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

I fudged a bit here by assuming that our bit counter always starts at 0. If it

started instead at N

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

cost (in bit ﬂips) could be as mu ch 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ﬁn e Φ

= 0, keep other values of the Φ

the s ame

(the number of 1-bits before the i

operation, and ﬁnally d eﬁ ne a

= c

+ Φ

. In

eﬀect, we charge a

with the start-up costs of our counting sequence. Of course, 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 the problem’s complexity. Th at 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-possib le

剩余248页未读，继续阅读

luckyfancy

粉丝: 0
资源: 15

Java数据结构与算法分析

data structure & algorithms in java

Java.9.Data.Structures.and.Algorithms.2017.4.pdf

ods-java-data-struction.pdf

Data Structures & Algorithms In Java.pdf

Data Structures And Algorithms in Java.pdf

Data Structures And Algorithms In Java.pdf

Guide to Data Structures_A Concise Introduction Using Java-Springer(2017).pdf

Schaums.Outline.of.Data.Structures.with.Java.2nd.Edition.Jun.2007

Addison.Wesley.Data.Structures.and.Algorithm.Analysis.in.Java.3rd.Edition.2011

Fundamentals of OOP and Data Structures in Java.pdf

最新资源