老师您好，在您的第四章链表这里提一个小问题
来源：14-6 哈希表的动态空间处理与复杂度分析。
绫清竹
2018-10-22
链表的插入，删除，这两个功能的操作的时间复杂度是O1，而他们要想完成操作必须移动指针去找到想要进行操作的位置，时间复杂度On这样算下来，不能以最好的情况考虑平均下来，插入删除的时间复杂度不是On吗？
写回答
1回答
-
不可以。这是因为我们确实能找到一个测试用例，让每一次插入删除都是O(n)。
请注意，这是和我们讲动态数组时的均摊复杂度不同。均摊复杂度我们之所以可以做均摊分析，不是因为考虑了最好的情况（最好的情况都不需要触发扩容缩容操作），而是在最坏的情况下，我们也能进行均摊，在最坏的情况下，n组操作中，也只有一个操作是O(n)的，其他操作是O(1)的，从而均摊来看，每个操作都是O(1)的：）
032018-10-23
相似问题