顺序表中基本操作的实现 初始化操作InitList Sq 查找元素操作LocateItem Sq O(n) 插入元素操作ListInsert Sq O(n) 删除元素操作ListDelete_Sq O(n) 归并操作MergeList_Sq O(n+m) 1/算法2.7 对比算法2.22.72.12 插入和删除操作的时间分析： Ein=∑p(n-i+l)=n/2 Edl=p(n-i)=(n-1)/2 23 ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 初始化操作 InitList_Sq 查找元素操作 LocateItem_Sq O(n) 插入元素操作 ListInsert_Sq O(n) 删除元素操作 ListDelete_Sq O(n) 归并操作MergeList_Sq O(n+m) //算法2.7 插入和删除操作的时间分析： Ein=Σpi (n-i+1)=n/2 Edl=Σpi (n-i)=(n-1)/2 顺序表中基本操作的实现 对比算法2.2 2.7 2.12
查找元素操作 时间复杂度O(n) 例如：顺序表 L.elem L.listsize 23754138546217 t.ip L.length =7 8 e= 38 返回值=4 e=50 返回值=0 3 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 查找元素操作 时间复杂度O(n) 例如：顺序表 23 75 41 38 54 62 17 L.elem L.length = 7 L.listsize e = 38 p p p p p i 12348 e = 50 p 返回值 = 4 返回值 = 0
插入元素操作 时间复杂度On) (a1,…,a-,a,…,an)改变为 (a1,...,ai1e,ai,an) <ai ai <aip,e>,<e,ap aj a2 a-1 a ⑦0 a a ai-1 e a ●● 表的长度增加 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 (a1 , …, ai-1 , ai , …, an ) 改变为 a1 a2 … ai-1 ai … an a1 a2 … ai-1 e ai … an <ai-1 , ai > <ai-1 , e>, <e, ai > 表的长度增加 (a1 , …, ai-1 , e, ai , …, an ) 插入元素操作 时间复杂度O(n)
删除元素操作时间复杂度0n)） (a1,,a-1,a,a+1…,an)改变为 (a1,,a-i,a+1,…,an) <ai-1va>,<a,a+1> <a-1ya+1 a a ai1 ai a+1 a a ●●● ai-lait1…an 表的长度减少 3 ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 删除元素操作 时间复杂度O(n) (a1 , …, ai-1 , ai , ai+1, …, an ) 改变为 ai+1 … an <ai-1 , ai >, <ai , ai+1> <ai-1 , ai+1> 表的长度减少 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 (a1 , …, ai-1 , ai+1, …, an )
顺序表其它算法举例* >比较两个顺序表的大小（逐个比较元素字符） 时间复杂度OMin(A.length,B.length) >用尽量少得辅助空间将前m个元素和后n个元 素互换 -exchangel时间复杂度.Omxn, -invert时间复杂度：Oi-s+l) -exchange.2时间复杂度：Om+n 注意：代码简洁和效率是两回事 23 ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 ➢比较两个顺序表的大小 (逐个比较元素字符) 时间复杂度O(Min(A.length,B.length)) ➢用尽量少得辅助空间将前m个元素和后n个元 素互换 – exchange1 时间复杂度：O(m×n) – invert 时间复杂度：O(t-s+1) – exchange2 时间复杂度：O(m+n) 顺序表其它算法举例* 注意：代码简洁和效率是两回事