algorithm - 償却分析会計方法

Question

i が正確に 3 の累乗である場合、i 番目の操作のコストが i であり、そうでない場合は 1 であるデータ構造に対する n 操作のシーケンスで、操作ごとの償却コストを見つけようとしています。

誰も私に問題を解決する方法を説明できますか

O(6) を見つけました。それが正しいか間違っているかわかりません。

Answer 1

特定の に対して、 cost を持つ「高価な」操作がnあり、残りはそれぞれを必要とします。floor(log_3(n))iO(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)

Big-Oh 記法は定数要素から離れて抽象化されているためO(6)、あまり意味がないことに注意してください。