线性表中的时间复杂度

线性表

一、顺序表示的线性表

1. 插入操作的时间复杂度
   • 最好情况：$O(1)$。（新元素插到表尾，不需要移动元素）
   • 最坏情况：$O(n)$。（新元素插到表头，需要将原有的n个元素全部向后移动）
   • 平均情况：$O(n)$。（假设新元素插到每个位置的概率相同$(p=\frac{1}{n+1})$，则平均循环次数为 $np+(n-1)p+...+1p=\frac{n(n+1)}{2}\frac{1}{n+1}=\frac{n}{2}$
2. 删除操作
   • 最好情况：$O(1)$。（删除表尾元素，不需要移动其他元素）
   • 最坏情况：$O(n)$。（删除表头元素，需要将后序的n-1个元素全部向前移动）
   • 平均情况：$O(n)$。（假设删除任何一个元素的概率相同$(p=\frac{1}{n})$，则平均循环次数为 $(n-1)p+(n-2)p+...+1p=\frac{n(n-1)}{2}\frac{1}{n}=\frac{n-1}{2}$
3. 按位查找：$O(1)$（由于顺序表各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素–“随机存取”特性）
4. 按值查找：
   • 最好情况：$O(1)$。（目标元素在表头）
   • 最坏情况：$O(n)$。（目标元素在表尾）
   • 平均情况：$O(n)$。（假设目标元素出现在任何一个位置的概率相同$(p=\frac{1}{n})$，则平均循环次数为 $1p+2p+...+np=\frac{n(n+1)}{2}\frac{1}{n}=\frac{n+1}{2}$

二、链式表示的线性表

单链表

1. 插入：
   • 按位序插入
     • 最好情况：$O(1)$（插在表头）
     • 最坏情况：$O(n)$（插在表尾）
     • 平均情况：$O(n)$
   • 指定节点的后插操作：$O(1)$
   • 指定节点的前插操作：
     • $O(n)$（循环查找指定节点p的前驱q，再对q后插）
     • $O(1)$（若在p节点前插入s，则先将s插到p后面，再交换p和s的数据域）
2. 删除：
   • 按位序删除
     • 最好情况：$O(1)$
     • 最坏、平均情况：$O(n)$
   • 指定节点的删除：$O(1)$
3. 查找
   • 按位查找：平均情况$O(n)$
   • 按值查找：平均情况$O(n)$
4. 求表长：$O(n)$
5. 单链表的建立
   • 头插法：（插入n个节点的时间复杂度为）$O(n)$
   • 尾插法：
     • 若不带表尾指针，则每次插入都从头遍历，时间复杂度为$O(n^2)$
     • 若设置一个表尾指针，则为$O(n)$

双链表

与单链表一样，双链表不可随机存取，按位查找、按值查找都只能用遍历的方式实现，时间复杂度$O(n)$

循环链表

1. 从尾部找到头部，时间复杂度是$O(1)$；从头节点找到尾部，时间复杂度是$O(n)$

栈

一、顺序存储实现的栈

基本操作（创建、增、删、查）都是$O(1)$的时间复杂度
对于栈的销毁，在函数运行结束后由系统自动回收内存