sorting - 排序链表的摊销界限

Question

我试图证明在排序的LinkedList 中插入操作的摊销复杂度是 O(1)。我知道最坏的情况时间是 O(n) 但很难找到合适的潜在函数。如果有人可以提供帮助，我会很高兴。

谢谢。

Answer 1

O(1) 摊销意味着在最坏的情况下，n 次插入的序列花费 O(n) 时间。对于这种情况，情况并非如此，因为以相反的顺序插入元素需要 O(n*n)。