algorithm - 摊销分析法

Question

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

谁能解释我如何解决这个问题

我找到了 O(6)，我不知道它是正确的还是错误的。

Answer 1

对于给定的n，有一些floor(log_3(n))“昂贵的”操作与 cost 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)没有多大意义。