Dsa Using Java 简明教程

DSA using Java - Overview

What is a Data Structure?

数据结构是组织数据的一种方法，可以有效地利用数据。以下术语是数据结构的基础术语。

  1. Interface − 每个数据结构都有一个接口。接口表示数据结构支持的操作集合。接口仅提供支持操作的列表、可以接受的参数类型和这些操作的返回类型。

  2. Implementation − 实现提供了数据结构的内部表示形式。实现还提供了数据结构操作中使用的算法定义。

Characteristics of a Data Structure

  1. Correctness − 数据结构实现应正确地实现其接口。

  2. Time Complexity − 数据结构操作的运行时间或执行时间必须尽可能小。

  3. Space Complexity − 数据结构操作的内存使用量应尽可能小。

Need for Data Structure

随着应用程序变得复杂且数据丰富，如今应用程序面临三个常见问题。

  1. Data Search − 考虑一家商店有 100 万 (106) 件库存。如果应用程序要搜索一个项目。它必须在 100 万 (106) 个项目中每次搜索一个项目，从而降低搜索速度。随着数据增长，搜索将变得更加缓慢。

  2. Processor speed − 处理器速度虽然很高，但如果数据增长到几十亿条记录，就会受到限制。

  3. Multiple requests − 由于数千名用户可以在 Web 服务器上同时搜索数据，因此即使非常快的服务器在搜索数据时也会遇到故障。

为了解决上述问题，数据结构派上了用场。可以将数据组织到数据结构中，使得可能无需搜索所有项目，并且可以几乎立即搜索所需数据。

Execution Time Cases

有三个案例通常用于以相对的方式比较各种数据结构的执行时间。

  1. Worst Case − 这是特定数据结构操作花费最多时间的情况。如果一个操作的最坏情况时间是 ƒ(n)，那么这个操作不会花费超过 ƒ(n) 次时间，其中 ƒ(n) 表示 n 的函数。

  2. Average Case − 这是描述数据结构操作的平均执行时间的情况。如果一个操作执行时间为 ƒ(n)，那么 m 个操作将花费 mƒ(n) 时间。

  3. Best Case − 这是描述数据结构操作最可能的执行时间的情况。如果一个操作执行时间为 ƒ(n)，那么实际操作可能需要的时间是一个随机数，该随机数最多为 ƒ(n)。