顺序数组插入、删除元素的时间复杂度

来源：5-2 二分搜索树基础（Binary Search Tree）

小懒猫学编程

2017-02-21

老师你好！对于顺序数组，插入元素和删除元素操作的时间复杂度为什么是O（n）级别呢？如果用二分法不是可以实现O（logn）级别吗？

写回答

2回答

liuyubobobo

2017-02-21

已采纳

嗯可以用O(logn)的时间复杂度找到要插入的元素位置或者要删除的元素位置。但是关键是，对于数组实现来说，不管是添加还是删除元素以后，还需将之后的所有元素进行前移和后移，才能保持他是一个数组啊。这部分操作是O(n)的复杂度。

小懒猫学编程

非常感谢！

2017-02-21

共1条回复

小懒猫学编程

提问者

2017-02-21

明白了，谢谢老师！

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 2

回答 1

回答 1

回答 1