701 查找的基本概念

查找的基本概念

查找表

静态查找表

定义: 仅进行查询操作的查找表。

操作:

1. 查询 (Search): 查找关键字为给定值的记录。
2. 统计 (Retrieve): 检索满足特定条件的记录。

特点: 数据集合固定，不涉及插入和删除操作。

动态查找表

定义: 在查找过程中同时进行插入或删除操作的查找表。

操作:

1. 查找 (Search): 查找关键字为给定值的记录。
2. 插入 (Insert): 向查找表中添加新的记录。
3. 删除 (Delete): 从查找表中移除指定记录。

特点: 数据集合是动态变化的。

平均查找长度 (Average Search Length, ASL)

定义: 在查找过程中，对给定关键字序列，进行比较的关键字的平均次数。

计算公式:

$$ASL=\sum _{i=1}^n{P}_i{C}_i$$

其中：

• $n$ 为查找表中记录的个数。
• $P_i$ 为查找第 $i$ 个记录的概率，通常假设每个记录被查找的概率相等，即 $P_i=1/n$。
• $C_i$ 为查找第 $i$ 个记录所需的比较次数。

分类:

1. 成功查找的平均查找长度 ($AS{L}_{succ}$): 查找表中存在的元素被找到所需的平均比较次数。 $$AS{L}_{succ}=\sum _{i=1}^n{P}_i{C}_i$$

若每个记录查找概率相等，则 $ASL_{succ} = \frac{1}{n} \sum_{i=1}^{n} C_i$。 2. **不成功查找的平均查找长度 ($ASL_{unsucc}$)**: 查找表中不存在的元素被判定为不存在所需的平均比较次数。 * 需要考虑所有可能的不成功查找情况。 **重要性**: 衡量查找算法效率的重要指标。ASL 越小，查找算法的效率越高。 **影响因素**: * **数据组织方式**: 数据的存储结构（如顺序表、树、哈希表）。 * **查找方法**: 采用的查找算法（如顺序查找、二分查找、哈希查找）。 * **查找概率**: 各个记录被查找的概率分布。 * **表长**: 查找表中记录的数量 $n$。