企业官网建设流程全解析

基本概念

查找—— 在数据集合中寻找满足某种条件的数据元素的过程称为查找

• 若找到，称为查找成功；若表中不存在，称为查找失败。

查找表（查找结构）—— 用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成

• 它是一个集合，元素间无明显的逻辑顺序（除非特意有序）。

关键字—— 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。(如id)

• 主关键字（唯一，如学号）可唯一识别一条记录；
• 次关键字（不唯一，如性别）可识别多条记录。

对查找表的常见操作：
①查找符合条件的数据元素
静态查找表：只支持查找/检索（如顺序表）【仅关注查找速度即可】

②插入、删除某个数据元素
动态查找表：支持插入/删除（如二叉排序树）【除了查找速度，也要关注插入、删除是否方便实现】

查找算法的评价指标

查找长度——在查找运算中，需要对比关键字的次数称为查找长度

平均查找长度（ASL）——所有查找过程中进行关键字的比较次数的平均值【ASL的数量级反应了查找算法时间复杂度】

A S L = ∑ i = 1 n P i C i \boldsymbol{ASL=\sum_{i=1}^n P_i C_i}ASL=∑i=1n​Pi​Ci​

• n nn：表中元素个数
• P i P_iPi​：查找第 i 个元素的概率，∑ P i = 1 \sum P_i=1∑Pi​=1；通常默认查找一个元素为等概率 -P i = 1 n P_i=\dfrac1nPi​=n1​
• C i C_iCi​：找到第 i 个元素需要比较关键字的次数（查找长度）

【评价一个查找算法的效率时，通常考虑查找成功 / 查找失败两种情况的ASL】

总结