攤銷分析

Question

在攤銷分析中。

平均案例運行時間：一種算法（操作）的所有可能輸入的平均值。 如果使用概率，稱爲預計運行時間

預計時間和攤銷時間有什麼不同？

Answer 1

預期時間：

我們做一些假設，並根據這些假設，我們做出的運行時間語句。

哈希表就是這樣一個例子。我們假設數據分佈良好，並聲稱操作的運行時間爲O（1），而操作的最壞情況運行時間實際上是O（n）。

分期時間：

即使一個操作可能會比某些給定的時間較長，在多個操作的時候會抵消給予提到的運行時間。

（很好實現）自調整大小的數組就是一個這樣的例子。插入時，需要O（n）調整數組的大小，但是，在許多插入中，每個插入平均需要O（1）。