Java 9数据结构与算法实战指南

需积分: 11 100 浏览量更新于2024-07-18 收藏 2.3MB PDF 举报

"Java 9 Data Structures and Algorithms" 是一本关于Java 9中数据结构和算法的详细指南，由Debasish Ray Chawdhuri编写，2017年出版。本书旨在深入浅出地介绍数据结构和算法，帮助读者理解并掌握这些核心概念。在Java 9这一特定版本的上下文中，书中的内容将帮助开发者提升程序性能和效率。第一章 "Why Bother? – Basic" 引导读者了解算法性能的重要性。首先，书中讨论了算法性能的三种情况：最佳情况、最差情况和平均情况复杂度。这些复杂度分析对于预测算法在不同输入规模下的行为至关重要。接着，书中介绍了渐进复杂度分析，这是一种评估算法时间复杂度的方法，特别是上界（asymptotic upper bound）和下界（asymptotic lower bound）的概念。渐进上界表示算法执行时间的上限，而下界则表示其理论上的最低限。当上下界相等时，我们称其为渐进紧界（asymptotic tight bound）。优化算法是提高代码效率的关键，书中提到了如何通过改进大数运算和减少时间复杂度来优化算法。第二章 "Cogs and Pulleys – Building Blocks" 开始介绍数据结构的基础，首先是数组。数组是最基本的数据结构之一，用于存储同类型的元素集合。书中详细描述了如何在数组中插入元素，包括在末尾追加新元素的过程。然后，书中转向链表，这是一种动态数据结构，允许高效地在任意位置插入和删除元素。链表分为单链表和双链表，书中可能涵盖了它们的基本操作，如在链表尾部添加元素、在链表开头插入元素以及在任意位置插入元素。后续章节可能会涵盖更多高级数据结构，如栈、队列、树（二叉树、平衡树、堆等）、图以及排序和搜索算法（如冒泡排序、快速排序、二分查找等）。此外，还可能涉及动态规划、递归、贪心算法和回溯等算法设计策略。 "Java 9 Data Structures and Algorithms" 是一本全面的教程，旨在帮助Java开发人员理解和应用各种数据结构和算法，以提高软件性能和解决复杂问题的能力。通过阅读本书，读者不仅可以增强理论知识，还能获得实践技能，从而在实际项目中实现更高效、更优化的代码。

Why Bother? – Basic

[ 4 ]

Analysis of asymptotic complexity

We seem to have hit upon an idea, an abstract sense of the running time. Let's spell it

out. In an abstract way, we analyze the running time of and the space required by a

program by using what is known as the asymptotic complexity.

We are only interested in what happens when the input is very large because it really

does not matter how long it takes for a small input to be processed; it's going to be

small anyway. So, if we have x

+ x

, and if x is very large, it's almost the same as x

We also don't want to consider constant factors of a function, as we have pointed

out earlier, because it is dependent on the particular hardware we are running the

program on and the particular language we have implemented it in. An algorithm

implemented in Java will perform a constant times slower than the same algorithm

written in C. The formal way of tackling these abstractions in dening the complexity

of an algorithm is called an asymptotic bound. Strictly speaking, an asymptotic

bound is for a function and not for an algorithm. The idea is to rst express the time

or space required for a given algorithm to process an input as a function of the size of

the input in bits and then looking for an asymptotic bound of that function.

We will consider three types of asymptotic bounds—an upper bound, a lower bound

and a tight bound. We will discuss these in the following sections.

Asymptotic upper bound of a function

An upper bound, as the name suggests, puts an upper limit of a function's growth.

The upper bound is another function that grows at least as fast as the original

function. What is the point of talking about one function in place of another? The

function we use is in general a lot more simplied than the actual function for

computing running time or space required to process a certain size of input. It is a lot

easier to compare simplied functions than to compare complicated functions.

For a function f, we dene the notation O, called big O, in the following ways:

1. f(x) = O(f(x)).

° For example, x

= O(x

2. If f(x) = O(g(x)), then k f(x) = O(g(x)) for any non-zero constant k.

° For example, 5x

= O(x

) and 2 log x = O(log x) and -x

= O(x

)

(taking k= -1).

Why Bother? – Basic

[ 8 ]

Asymptotic upper bound of an algorithm

Okay, so we gured out a way to sort of abstractly specify an upper bound on

a function that has one argument. When we talk about the running time of a

program, this argument has to contain information about the input. For example,

in our algorithm, we can say, the execution time equals O(power). This scheme of

specifying the input directly will work perfectly ne for all programs or algorithms

solving the same problem because the input will be the same for all of them.

However, we might want to use the same technique to measure the complexity of

the problem itself: it is the complexity of the most efcient program or algorithm that

can solve the problem. If we try to compare the complexity of different problems,

though, we will hit a wall because different problems will have different inputs.

We must specify the running time in terms of something that is common among

all problems, and that something is the size of the input in bits or bytes. How

many bits do we need to express the argument, power, when it's sufciently large?

Approximately log

(power). So, in specifying the running time, our function needs

to have an input that is of the size log

(power) or lg (power). We have seen that the

running time of our algorithm is proportional to the power, that is, constant times

power, which is constant times 2 lg(power) = O(2x),where x= lg(power), which is the

the size of the input.

Asymptotic lower bound of a function

Sometimes, we don't want to praise an algorithm, we want to shun it; for example,

when the algorithm is written by someone we don't like or when some algorithm

is really poorly performing. When we want to shun it for its horrible performance,

we may want to talk about how badly it performs even for the best input. An a

symptotic lower bound can be dened just like how greater-than-or-equal-to can be

dened in terms of less-than-or-equal-to.

A function f(x) = Ω(g(x)) if and only if g(x) = O(f(x)). The following list shows a

few examples:

• Since x

= O(x

), x

= Ω(x

)

• Since x

= O(5x

), 5x

= Ω(x

)

• Since x

= O(5x

- 25x

+ 1), 5x

- 25x

+ 1 = Ω(x

)

• Since x

= O(x

), x

= O(x

)

Again, for those of you who are interested, we say the expression f(x) = Ω(g(x))

means there exist positive constants M and x

, such that |f(x)| > M|g(x)| whenever

x > x

, which is the same as saying |g(x)| < (1/M)|f(x)| whenever x > x

, that is, g(x)

= O(f(x)).

剩余326页未读，继续阅读

J-10

粉丝: 18
资源: 484

Java 9数据结构与算法实战指南

"数据结构与算法分析（Java语言描述）习题答案第三版

Java源码解读：深入理解Data.Structures.and.Algorithms

Java中的数据结构与算法解析

Java 9 Data Structures and Algorithms epub

Java 9 Data Structures and Algorithms 无水印pdf

Data Structures and Algorithms in Java

Data Structures And Algorithms in Java

Data structures and Algorithms in Java

Data Structures And Algorithms in Java 2005

Java Data Structures and Algorithms In Action. Java数据结构和算法实战.zip

最新资源