数据结构 : 数组 / 链表 / 二叉排序树增删改查的时间复杂度解析_思考分析二叉链表遍历的算法时间复杂度

我们先看一下时间复杂度的概念:

    在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。
记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。

接下来我们对比一下数组 / 链表 / 二叉树增删改查的时间复杂度

一.数组

数组长度设为n

1.正常数组:

增改查:
既然知道数值对应的下标,那么我们要想找到一个数组中的数,只需要锁定其下标,对它进行增改查操作即可.所以这是一步锁定的操作.
则这种情况下增改查的时间复杂度是 O(1).

删:
一步锁定找到想要删除的数值,进行删除,然后需要移动删除部分后面的数值,如果该数值在数组头部,则需要移动n次,若在尾部,则无需移动,取一个平均值则需要n/2次,忽略常数,所以删操作的时间复杂度是 O(n).

2.无下标数组:

不知道数值的对应下标的数组,我们简称为无下标的数组,不知道所要操作的数值在数组的什么地方,这就需要我们去数组遍历寻找,然后进行操作.

增:
数组是地址连续存储的,所以对数组进行增操作,只要在数组尾部增加即可,一步到位,所以增操作的时间复杂度是 O(1).

删:
要遍历找到想要删除的数值,进行删除,如果该数值在数组头部,则需要遍历一次,若在尾部,则需要遍历n次,取一个平均值则需要遍历n/2次,忽略常数,所以删操作的时间复杂度是 O(n).

改:
改操作同删除操作类似,要遍历找到想要更改的数值,进行更改,所以改操作的时间复杂度是 O(n).

查:
查操作也同上,时间复杂度是 O(n).

3.有序无下标数组:

查:
这里我们先说查操作,计算机在进行操作时,会选择使用最优的方法解决问题,我们这里的数组是有序的,所以使用 二分查找 比遍历查找更快,其平均查找次数是log₂n.
实际上由于所有的对数都和其他对数成比例(从底数位2转换到底数位10需乘以3.332)，我们可以将这个为常数的底数也可忽略。由此不必指定底数：时间复杂度是 log(n).

增:
针对有序无下标的数组,不能随意在尾部添加数据,应该找到数据适合添加的位置,平均查找次数是平均查找次数是log₂n,找到该位置后,还要将插入位置后面的数组进行后移操作,平均移动次数也是n/2,相加则平均进行n/2+log₂n次操作,时间复杂度取最大值,则增操作的时间复杂度是 O(n).

删:
删操作同样针对有序无下标的数组,要遍历找到想要删除的数值,进行删除,平均查找次数是log₂n,找到该位置后删除,还要将删除位置后面的数组进行前移操作,平均移动次数是n/2,同理删操作的时间复杂度是 O(n).

改:
改操作同删除操作类似,要遍历找到想要更改的数值,进行更改,平均查找次数是log₂n,还要将该更改的数找到合适的位置移动排序,平均查找次数是n/2,所以改操作的时间复杂度是 O(n).

二.链表

设链表长度为n

1.单向无序链表:

增:
链表是通过记录头部地址来进行寻找后面数值的,所以需要遍历链表操作,如果在头部增,只需要查找一次,时间复杂度是 O(1),在尾部增需要查找n次,时间复杂度是 O(n).

删:
要遍历找到想要删除的数值,进行删除,对于链表,我们没法使用二分查找,只能遍历查找,找到该节点后删除,平均查找次数是n/2,时间复杂度是 O(n).

改:
要遍历找到想要更改的数值,同样只能遍历查找,平均查找次数是n/2,时间复杂度是 O(n).

查:
要遍历查找,同样只能遍历查找,平均查找次数是n/2,时间复杂度是 O(n).

2.单向有序链表:

增:
针对有序链表操作,需要保持其有序的原则,遍历链表找到该数值所在节点可以增加的位置,平均查找次数是n/2,时间复杂度是 O(n).

删:
通过遍历查找,找到该节点后删除,平均查找次数是n/2,时间复杂度是 O(n).

改:
通过遍历查找,找到想要更改的数值,同样只能遍历查找,平均查找次数是n/2,然后需要根据有序原则,为该节点寻找适合的位置进行移动,平均查找时间是n/2,时间复杂度是 O(n).

查:
要遍历查找,同样只能遍历查找,平均查找次数是n/2,时间复杂度是 O(n).

三. 二叉排序树:

二叉排序树又称二叉查找树，它或是一棵空的二叉树，或是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有节点的值均小于根节点的值
若它的右子树不空，则右子树上所有节点的值均大于根节点的值
它的左右子树也都是二叉排序树

查:
给定值的比较次数等于给定值节点在二叉排序树中的层数。如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为log₂n +1,其查找效率为O(log₂n)，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在O(log₂n)到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。

增/删/改:
同理如查

四.总结

该表时间复杂度是根据已知数值,对数组 / 链表 / 二叉树进行操作的总结: