数据结构与算法 - 概述

数据结构是一种组织数据以有效使用数据的系统方法。以下术语是数据结构的基础术语。

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

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

数据结构的特征

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

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

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

对数据结构的需求

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

  • 数据搜索- 考虑商店的100 万（10 6 ）件商品的库存。如果应用程序要搜索一个项目，则每次都必须在 100 万（10 6 ）个项目中搜索一个项目，这会减慢搜索速度。随着数据的增长，搜索会变得更慢。

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

  • 多个请求- 由于数千个用户可以在 Web 服务器上同时搜索数据，因此即使是快速服务器在搜索数据时也会失败。

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

执行时间案例

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

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

  • 平均情况- 这是描述数据结构操作的平均执行时间的场景。如果执行一个操作需要 f(n) 时间，则 m 个操作将花费 mf(n) 时间。

  • 最佳情况- 这是描述数据结构操作的最短可能执行时间的场景。如果执行操作需要 f(n) 时间，则实际操作可能需要时间作为随机数，该随机数最大为 f(n)。

基本术语

  • 数据- 数据是值或值集。

  • 数据项- 数据项是指单个值单位。

  • 组项- 分为子项的数据项称为组项。

  • 基本项- 无法分割的数据项称为基本项。

  • 属性和实体- 实体是包含某些可以分配值的属性或属性的实体。

  • 实体集- 具有相似属性的实体形成实体集。

  • 字段- 字段是表示实体属性的单个基本信息单元。

  • 记录- 记录是给定实体的字段值的集合。

  • 文件- 文件是给定实体集中实体记录的集合。