Java 数据结构与算法 - 概述

什么是数据结构？

数据结构是一种以特定方式组织数据，以便高效使用的方法。以下术语是数据结构的基础术语。

• 接口 - 每个数据结构都有一个接口。接口表示数据结构支持的操作集。接口仅提供支持的操作列表、它们可以接受的参数类型以及这些操作的返回类型。

• 实现 - 实现提供了数据结构的内部表示。实现还提供了数据结构操作中使用的算法的定义。

数据结构的特征

• 正确性 - 数据结构实现应正确实现其接口。

• 时间复杂度 - 数据结构操作的运行时间或执行时间应尽可能短。

• 空间复杂度 - 数据结构操作的内存使用量应尽可能少。

数据结构的必要性

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

• 数据搜索 - 考虑一个商店拥有 100 万 (10⁶) 件商品的库存。如果应用程序要搜索一件商品。它每次都必须在 100 万 (10⁶) 件商品中搜索商品，从而减慢搜索速度。随着数据量的增长，搜索会变得越来越慢。

• 处理器速度 - 尽管处理器速度非常高，但如果数据增长到数十亿条记录，它仍然会受到限制。

• 多请求 - 由于数千名用户可以同时在 Web 服务器上搜索数据，即使是最快的服务器在搜索数据时也会出现故障。

为了解决上述问题，数据结构可以提供帮助。数据可以以某种方式组织到数据结构中，这样就不需要搜索所有项目，并且可以几乎立即搜索所需的数据。

执行时间案例

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

• 最坏情况 - 这是特定数据结构操作可能花费的最长时间。如果操作的最坏情况时间为 ƒ(n)，则此操作花费的时间不会超过 ƒ(n)，其中 ƒ(n) 表示 n 的函数。

• 平均情况 - 这表示数据结构操作的平均执行时间。如果操作执行时间为 ƒ(n)，则 m 个操作将花费 mƒ(n) 时间。

• 最佳情况 - 这表示数据结构操作的最小可能执行时间。如果操作执行时间为 ƒ(n)，则实际操作可能花费的时间为随机数，其最大值为 ƒ(n)。