老师您好，在您的第四章链表这里提一个小问题

Question

链表的插入，删除，这两个功能的操作的时间复杂度是O1，而他们要想完成操作必须移动指针去找到想要进行操作的位置，时间复杂度On这样算下来，不能以最好的情况考虑平均下来，插入删除的时间复杂度不是On吗？

Answer 1

liuyubobobo 2018-10-22 10:51:34

不可以。这是因为我们确实能找到一个测试用例，让每一次插入删除都是O(n)。

请注意，这是和我们讲动态数组时的均摊复杂度不同。均摊复杂度我们之所以可以做均摊分析，不是因为考虑了最好的情况（最好的情况都不需要触发扩容缩容操作），而是在最坏的情况下，我们也能进行均摊，在最坏的情况下，n组操作中，也只有一个操作是O(n)的，其他操作是O(1)的，从而均摊来看，每个操作都是O(1)的：）

• 提问者 绫清竹 #1

  那既然链表的插入删除复杂度也是On，顺序表(也就是我们的动态数组）插入删除也是On，那为什么还说，如果插入删除操作多，要用链表呢，复杂度都是On呀

• liuyubobobo 回复 提问者 绫清竹 #2

  这个说法不完全准确，要具体情况具体分析，可以参考这个问答：http://coding.imooc.com/learn/questiondetail/57677.html ：）

• 提问者 绫清竹 #3

  非常感谢！