打开主菜单

平摊分析

(重定向自平摊时间

平攤分析计算机科学中,是用於算法分析中的方法,平攤分析常用於分析資料結構(動態的資料結構),在使用平攤分析前須知道資料結構各種操作所可能發生的時間,並計算出最壞情况下的操作情況並加以平均,得到操作的平均耗费时間。平摊分析只能確保最坏情况性能的每次操作耗费的平均时间,並不能確認平均情况性能。

一個簡單的例子,一個長度為n的list,在list的最後要加入一筆新的資料此時要花費的操作時間為O(n),此時也是加入新的資料的最糟糕的情況。但是,一个 n 个插入的操作序列仍然可以在 O(n) 的时间内完成,因为剩下的插入可以在常数时间内完成,因此n 个插入可以在 O(n) 的时间内完成。因此每操作的平摊耗费为O(n) / n = O(1)。

注意平摊分析与平均时间分析和概率算法的概率分析不同。在平均时间分析中,我们平均化所有可能的输入;在概率算法的概率分析中,我们平均化所有可能的随机选择;在平摊分析中,我们平均化一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。[1]

平摊分析中几种常用的技术:

  • 聚合分析决定 n 个操作序列的耗费上界T(n),然后计算平均耗费为 T(n) / n[1]
  • 记账方法确定每个操作的耗费,结合它的直接执行时间及它在对运行时中未来操作的影响。通常来说,许多短操作增量累加成「债」,而通过减少长操作的次数来「偿还」。[1]
  • 势能方法类似记账方法,但通过预先储蓄「势能」而在需要的时候释放。[1]

平攤分析種類编辑

聚合方法编辑

記帳方法编辑

沖能方法编辑

勢能方法编辑

例子编辑

动态数组编辑

 
动态数组的平摊分析

考虑一个随元素个数增加而增长的动态数组,比如JavaArrayList或者C++std::vector。如果我们的数组大小从4开始,那么来向其中增加四个元素的时间就是一个常数。然而,若要将第五个元素加入其中,那么会花费更多时间,因为我们此时必须要创建一个两倍于当前数组大小的数组(8个元素),把老元素拷贝到新数组中,然后增加一个新元素。接下来的三次加入操作也同样会花费常数时间,然后在数组被填满后则又需要一轮新的加倍扩充。

一般地,如果我们考虑任意一个任意的n大小的数组并对其进行n + 1次加入操作。我们注意到,所有的加入操作都是常数时间的,除了最后一个,它会花费 时间在大小加倍上。因为我们进行了n + 1次加入操作,我们可以将数组加倍的时间平摊到所有的加入操作上,因此得到加入操作的平均时间是 。它是一个常数。[1]

队列编辑

使用Ruby實現的佇列,一个先進先出資料結構:

class Queue
  def initialize
    @input = []
    @output = []
  end

  def enqueue(element)
    @input << element
  end

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop
      end
    end

    @output.pop
  end
end

佇列操作及特性參考佇列條目,enqeue及deqeue操作時間複雜度為常數, 否則,dequeue需要 時間將所有元素從輸入數組添加到輸出數組中,其中n是輸入數組的當前長度。 從輸入複製n元素後,我們可以在輸出數組再次為空之前執行n出隊操作,每次操作都需要一個恆定的時間。 因此,我們可以僅在 時間執行一系列n出列操作,這意味著每個出列操作的攤銷時間是 [2]

或者,我們可以收取將任何項目從輸入數組複製到輸出數組的成本,以及該項目的早期排隊操作。 該計費方案將入隊的攤還時間加倍,但將出列的攤還時間減少到 

通常用法编辑

  • 在常见场合,我们把能很好平摊分析的算法称为“平摊算法”。
  • 在线算法通常使用平摊分析。

参考资料编辑

[3]

  1. ^ 1.0 1.1 1.2 1.3 1.4 Kozen, Dexter. CS 3110 Lecture 20: Amortized Analysis. Cornell University. Spring 2011 [14 March 2015]. 
  2. ^ Grossman, Dan. CSE332:Data Abstractions (PDF). cs.washington.edu. [2015年3月14日]. 
  3. ^ MIT 6.046J Design and Analysis of Algorithms, Spring 2015. MIT. [2018/10/21].