2. 基本非数值算法
# 查找
# 查找基本概念
平均查找长度(ASL) 是衡量查找算法效率的重要指标,其计算公式为:
ASL=∑PiCiASL = \sum P_i C_iASL=∑PiCi
其中,PiP_iPi 是第 iii 条记录的查找概率,CiC_iCi 是第 iii 条记录的查找长度。
# 线性表查找
线性表查找主要包括顺序查找和折半查找。不同数据结构的线性表在查找、插入和删除操作上的效率差异显著:
数据结构
查找
插入
删除
无序顺序表
O(n)O(n)O(n)
O(1)O(1)O(1)
O(n)O(n)O(n)
无序线性链表
O(n)O(n)O
more...




