關於攤銷分析

Question

這是關於攤銷分析。以下是文章中的文字。

對於需要執行一系列操作的問題的攤銷分析，我們的目標是分析每個操作的時間。攤銷分析的動機在於，如果產生價格昂貴的唯一方法是預先用大量廉價操作「設置」，則每個操作的最壞情況時間爲 時間可能過於悲觀。

問：什麼是作者的最後一句話的意思，即「如果只有這樣才能產生昂貴的是‘’有大量的前 手賤操作的」設置？任何人都可以用例子來解釋這個陳述的意思嗎？

謝謝！

Answer 1

另一個例子。考慮一個數組，當添加一個超過當前容量的元素時，它會動態增加其容量。讓容量增加爲O（n），其中n是陣列的舊尺寸。現在，添加元素的最壞情況複雜度爲O（n），因爲我們可能需要增加容量。分期分析背後的想法是，你必須做一些簡單的加法，在容量耗盡之前花費O（1）。因此，許多便宜的操作導致了昂貴的操作。換句話說，昂貴的操作是由廉價的操作攤銷。

Answer 2

作者的意思是昂貴的操作可能發生的唯一方法是在大量的廉價操作之前。

看看這個例子： 我們有一個堆棧，除了通常的操作外，我們還希望堆棧實現，還有一個稱爲multipop（k）的操作，用於彈出k個元素。現在，multipop成本O（min（n，k）），其中n是堆棧的大小;因此，例如O（k）的multipop對成本的先決條件是至少k個廉價推送，每個成本O（1）。