本文主要是介绍顺序表与链表时间复杂度比较，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
顺序表与链表时间复杂度比较
| 名称 | 访问 | 查找 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) |
| 有序数组 | O(1) | O(logN) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1) | O(1) |
| 有序链表 | O(n) | O(n) | O(n) | O(n) |
1、向一个有序数组中插入一个数的时间复杂度是多少?
第一步：确定插入的位置。采用遍历查找的时间复杂度是O(n)，采用二分查找的时间复杂度是O(log2n)。
第二步：插入元素。在进行插入操作时需要将该元素后的每一位元素后移一位，这步操作的时间复杂度为O(n)。
综上向一个有序数组中插入一个数的时间复杂度是O(n)。
O(n)+O(n)=O(n)，O(log2n)+O(n)=O(n)）
2、有序链表查找的时间复杂度是O(n)的原因是什么？
链表采用二分查找的效率不能达到O(logN)。只有当访问集合中任何一个元素的时间是常量O(1)时，二分查找才能达到O(logN)，而链表访问其中元素的平均时间是O(N)，故链表不能采用二分查找，只能用遍历查找。
用数组构造的集合才能使用折半查找。
这篇关于顺序表与链表时间复杂度比较的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
