Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我试图证明在排序的LinkedList 中插入操作的摊销复杂度是 O(1)。我知道最坏的情况时间是 O(n) 但很难找到合适的潜在函数。如果有人可以提供帮助,我会很高兴。
谢谢。
O(1) 摊销意味着在最坏的情况下,n 次插入的序列花费 O(n) 时间。对于这种情况,情况并非如此,因为以相反的顺序插入元素需要 O(n*n)。