有序堆棧的攤銷分析

我正在通過我在網上找到的教程工作表，並且遇到了一個我無法弄清楚如何解決的問題。有序堆棧的攤銷分析

的有序堆疊S是其中元素出現在遞增的順序堆疊。它支持以下操作：

Init（S）：創建一個空的有序堆棧。

流行（S）：刪除並返回排序堆棧中的頂層元素。（S，x）：在有序堆棧頂部插入x，並通過反覆移除x之下緊鄰的元素來重新建立遞增的順序，直到x爲堆棧上的最大元素爲。

銷燬（S）：刪除有序堆棧上的所有元素。

認爲所有操作的攤銷運行時間爲O（1）。誰能幫忙？

2014-09-11 veronik

作爲提示，請使用潛在函數。嘗試將潛力設置爲堆棧的高度。 – templatetypedef 2014-09-11 06:24:07

我想你可以做的是，

首先證明的init（S），POP（S）和destroy（）真的，其實需要O（1）時間（他們真的做的。）

然後對於推遲（S，x）函數，它將O（n）的複雜度漸漸增加到O（n），認爲push（）將以O（1）時間開始並繼續給出相同的複雜度，直到除非數字小於推入堆棧頂部。發生這種情況的可能性可以被計算來支持你的論點。

（如果有不正確的地方請做評論）

2014-09-11 10:51:01 Haris

銷燬處理堆棧中的每個元素。用於插入= K實際成本+ 1 潛力=樹的高度（N）攤餘成本= K + 1 +（N-K + 1） - （N）= 2 不知道該怎麼辦這這個。 – veronik 2014-09-12 04:29:14

回答