摊销分析法

Question

我试图在数据结构上的 n 个操作序列中找到每个操作的摊销成本，其中第 i 个操作成本 i 如果 i 是 3 的精确幂，否则为 1

谁能告诉我如何解决这个问题

我找到了O(6)，不知道对不对。

Answer 1

对于给定的 n，有 floor(log_3(n)) 'expensive' 次操作，成本为 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)

请注意，Big-Oh 符号从常数因子中抽象出来，因此 O(6) 没有多大意义。