已排序链表的摊销边界
amortized bound of sorted linked list
我试图证明 sorted LinkedList 中插入操作的分摊复杂度为 O(1)。
我知道最坏情况的时间是 O(n)，但发现很难找到合适的势函数。
如果有人能提供帮助，我会很高兴。
谢谢。
O(1) 摊销意味着在最坏的情况下，一系列 n 次插入花费 O(n) 时间。对于这种情况，情况并非如此，因为以相反的顺序插入元素需要 O(n*n).
我试图证明 sorted LinkedList 中插入操作的分摊复杂度为 O(1)。 我知道最坏情况的时间是 O(n)，但发现很难找到合适的势函数。 如果有人能提供帮助，我会很高兴。
谢谢。
O(1) 摊销意味着在最坏的情况下，一系列 n 次插入花费 O(n) 时间。对于这种情况，情况并非如此，因为以相反的顺序插入元素需要 O(n*n).