三、顺序表操作的效率分析 时间效率分析: 算法时间主要耗在移动元素的操作上,因此计算时 间复杂度的基本操作(最深层语句频度) T(n)=0(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置 注意:若插入在尾结点之后,则根本无需移动(特别快) 若插入在首结点之前,则表中元素全部要后移(特别慢) 应当考虑在各种位置插入(共n+1种可能)的平均移动次数才
1 三、 顺序表操作的效率分析 时间效率分析: 算法时间主要耗费在移动元素的操作上，因此计算时 间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置. 注意：若插入在尾结点之后，则根本无需移动（特别快）； 若插入在首结点之前，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才 合理
推导: 假定在毎个元素位置上插入x的可能性都一样(即概 率P相同),则应当这样来计算平均执行时间: 将所有位置的执行时间相加,然后取平均。 若在首结点前插入,需要移动的元素最多,后移n次; 若在a后面插入,要后移n-1个元素,后移次数为n-1 若在an-后面插入,要后移1个元素 若在尾结点an之后插入,则后移0个元素; 所有可能的元素移动次数合计: 0+1++n=n(n+1)/2 共有多少种插入形式?连头带尾有n+1种 故插入时的平均移动次数为: n(n+1)/2÷(n+1)=n/2≈0(m)
2 推导： 假定在每个元素位置上插入x的可能性都一样（即概 率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均。 若在首结点前插入，需要移动的元素最多，后移n次； 若在a1后面插入，要后移n-1个元素，后移次数为n-1; …… 若在an-1后面插入，要后移1个元素； 若在尾结点an之后插入，则后移0个元素； 所有可能的元素移动次数合计： 0+1+…+n = n(n+1)/2 共有多少种插入形式?——连头带尾有n+1种! 故插入时的平均移动次数为： n(n+1)/2÷（n+1）＝n/2≈O(n)
同理可证: 顺序表删除一元素的时间效率为 T(n)=(n-12≈0(n) 即插入、删除算法的平均时间复杂度为 O(n)
3 同理可证： 顺序表删除一元素的时间效率为: T(n)=(n-1)/2 ≈O(n) 即插入、删除算法的平均时间复杂度为 O(n)
简单回顾 线性表顺序存储结构特点:逻辑关系上相邻的两个元 素在物理存储位置上也相邻; 优点可以随机存取表中任一元素,方便快捷; 缺点:在插入或删除某一元素时,需要移动大量元素; 需要预先确定数据元素的最大个数。 解决问题的思路:改用另一种线性存储方式
4 简单回顾 线性表顺序存储结构特点：逻辑关系上相邻的两个元 素在物理存储位置上也相邻； 优点:可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素; 需要预先确定数据元素的最大个数。 解决问题的思路：改用另一种线性存储方式： 链式存储结构
23线性表的链式表示和实现 单链表的存储结构 二、单链表的操作实现 链表的运算效率分析
5 2.3 线性表的链式表示和实现 一、单链表的存储结构 二、 单 链表的操作实现 三、链表的运算效率分析