平攤分析計費方法

Question

我試圖找到每個操作中n個操作的一個序列上的數據結構的攤銷成本，其中第i個操作成本i若i爲3的精確功率，否則爲1

任何人都可以解釋我如何解決問題

我發現O（6），我不知道它是否正確或錯誤。

Answer 1

對於給定的n，有floor(log_3(n))「昂貴」的操作，成本爲i，其餘各需要O(1)。

O(1/n * (n - floor(log_3(n)) + sum_k=0..floor(log_3(n)) { 3^k })) 
= O(1/n * (n + (3^(floor(log_3(n))+1) - 1)/(3 - 1))) // applying the formula for a finite sum of a geometric series 
= O(1/n * (n + c * n)) 
= O(1) 

注意大哦符號的持續性因素抽象了，所以O(6)並沒有太大的意義。