文章目录
- 如何理解时间复杂度和空间复杂度
- 主要数据结构的时间空间复杂度
-
- 数组详解
- 链表
- 三. 二叉排序树:
如何理解时间复杂度和空间复杂度
- 时间复杂度是指执行算法所需要的
计算工作量
- 空间复杂度是指执行这个算法所需要的
内存空间
主要数据结构的时间空间复杂度
| 数据结构 | 增 | 删 | 改 | 查 | 空间复杂度 |
|---|---|---|---|---|---|
| 红黑树 | O（log N） | O（log N） | O（log N） | O（log N） | O(1) |
| 跳表 | O(logn) | O(logn) | O(logn) | O(logn) | O(n） |
| hash表 | O(1) | O(1) | O(1) | O(1) | O(1) |
数组详解
数组长度设为n
1.正常数组:
增改查：时间复杂度是 O(1).
删:
需要移动后面的数据 O(n).
2.无下标数组:
不知道数值的对应下标的数组,我们简称为无下标的数组,不知道所要操作的数值在数组的什么地方,这就需要我们去数组遍历寻找,然后进行操作.
增:
O(1).
删:
要遍历找到想要删除的数值,进行删除,如果该数值在数组头部,则需要遍历一次,若在尾部,则需要遍历n次,取一个平均值则需要遍历n/2次,忽略常数,所以删操作的时间复杂度是 O(n).
改:
改操作同删除操作类似,要遍历找到想要更改的数值,进行更改,所以改操作的时间复杂度是 O(n).
查:
查操作也同上,时间复杂度是 O(n).
3.有序无下标数组:
因为有序，所以增删改都需要保证顺序
查:
数组是有序的,所以使用
二分查找
比遍历查找更快,其平均查找次数是
logn.
增:
需要移动后面的数据 O(n).
删:
需要移动后面的数据 O(n).
改:
改操作同删除操作类似,要遍历找到想要更改的数值,进行更改,O(n).
4 有序有下标数组:
查：
O(1)
增删改：
同有序无下标数组
链表
设链表长度为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个节点的二叉排序树的高度为log2n +1,其查找效率为O(log2n)，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在O(log2n)到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。
增/删/改:
同理如查