非專業術語的攤銷複雜性？

Question

有人可以通過外行人的方式解釋分期付款的複雜性嗎？我一直很難在網上找到一個精確的定義，我不知道它是如何與算法分析完全相關的。任何有用的東西，即使外部引用，都會受到高度讚賞。

Answer 1

「分期付款複雜性」的原則是，雖然當你做這件事情時可能相當複雜，因爲它不經常做，它被認爲「不復雜」。例如，如果你創建一個需要時時平衡的二叉樹 - 比如每插入一個2^n一次 - 因爲雖然平衡樹是非常複雜的，但它只會在每次插入時發生一次（例如一次插入256次，然後再次在第512，第1024等）。在所有其他插入中，複雜度爲O（1） - 是的，每插入一次需要O（n），但它的概率僅爲1/n，所以我們將O（n）乘以1/n並得到O（1）。所以這被認爲是「O（1）的攤銷複雜性」 - 因爲當你添加更多的元素時，重新平衡樹所消耗的時間是最小的。

Answer 2

分期平均分攤重複運行。最壞情況的行爲保證不會發生很多頻率。例如，如果最慢的情況是O（N），但是發生這種情況的機會只是O（1/N），否則過程是O（1），那麼該算法仍然具有攤銷常數O（1）time 。只要考慮將每個O（N）運行的工作分成N個其他運行。

這個概念取決於有足夠的運行時間來劃分總時間。如果算法只運行一次，或者每次運行都必須滿足截止日期，那麼最壞情況下的複雜性更具相關性。

Answer 3

它有點類似於將算法中不同分支的最壞情況複雜度與執行該分支的概率相乘並添加結果。所以如果某個分支不太可能被採用，它對複雜性的貢獻就會降低。

Answer 4

攤銷複雜性爲每個操作的總費用，通過一系列操作進行評估。

這個想法是保證整個序列的總費用，同時允許單個操作比攤銷成本高得多。

實施例：
的C++ std::vector<>行爲。當push_back()將矢量大小增加到其預分配值以上時，它將分配的長度加倍。

所以單個push_back()可能需要O(N)時間來執行（作爲數組的內容被複制到新的存儲器分配）。

然而，因爲分配的規模增加了一倍，未來N-1調用push_back()將各自採取O(1)時間來執行。所以，總共N作業仍然需要O(N)次;從而給予push_back()每次操作的攤銷成本O(1)。

---

除非另有規定，攤銷複雜性是任何操作序列的漸近最壞情況保證。這意味着：

• 正如非攤銷的複雜性，用於攤銷複雜的大O符號忽略這兩個固定的初始開銷和持續性能的因素。因此，爲了評估大型O攤銷業績，您通常可以假定任何分期付款業務的順序將「足夠長」以分攤固定的啓動費用。具體而言，對於std::vector<>示例，這就是爲什麼您不必擔心是否會實際遇到N其他操作：分析的漸近性已經假定您會這樣做。

• 除了任意長度，平攤分析不使有關操作，其成本要測量的序列假設 - 它是操作的任何可能的序列最壞情況的保證。無論操作被選擇的程度如何嚴重（比如惡意的對手！），攤銷分析必須保證足夠長的一系列操作的花費不會超過其攤銷成本的總和。這就是爲什麼（除非特別提及爲限定詞）「概率」和「平均情況」與攤銷分析無關 - 不僅僅是它們對於普通的最壞情況的大O分析！

Answer 5

在平攤分析，以執行數據結構操作的序列需要被平均在所有的操作時執行...攤銷分析從平均情況分析不同之處在於概率是不參與;攤銷分析保證了最差情況下每項業務的平均業績。

（從Cormen等人，「算法導論」）

這可能是一個有點混亂，因爲它說兩者的時間平均，並且它不是一個平均情況分析。因此，讓我試着用一個財務比喻來解釋這個問題（事實上，「分期償還」一詞通常與銀行業務和會計相關。）

假設您正在經營彩票業務。 （不要購買彩票，我們稍後會獲得，但是會自己操作彩票。）您可以打印100,000張門票，每門門票售價爲1個貨幣單位。其中一張門票將使購買者獲得40,000個貨幣單位。

現在，假設您可以出售所有門票，您可以賺取6萬個貨幣單位：銷售額爲100,000貨幣單位，減去4萬貨幣單位獎金。對您而言，每張票的價值爲0.60個貨幣單位，在所有票上攤銷。這是一個可靠的價值;你可以在它上面存錢。如果您厭倦了自己出售門票，並且有人出面並提出以每個0.30個貨幣單位出售它們，那麼您確切知道自己的位置。

對於彩票購買者來說，情況是不同的。購買者在購買彩票時預計會損失0.60個貨幣單位。但這是概率性的：購買者可能會每天購買10張彩票30年（有點超過10萬張彩票）而沒有獲勝。或者他們可能會自發地購買一張票，並贏得39,999個貨幣單位。

應用於數據結構分析，我們討論的是第一種情況，我們在這種情況下分攤一些數據結構操作（比如插入）的成本。平均案例分析處理的是隨機操作（比如搜索）的預期值，我們無法計算所有操作的總成本，但我們可以提供單個預期成本的概率分析。

經常指出，攤銷分析適用於高成本操作罕見的情況，通常情況如此。但不總是。例如，考慮所謂的「銀行家隊列」，它是由兩個堆棧構成的先進先出（FIFO）隊列。 （這是一個經典的功能數據結構;你可以用不可變的單鏈節點構建廉價的LIFO棧，但廉價的FIFO不是那麼明顯）。的操作被實現如下：

put(x): Push x on the right-hand stack. 
y=get(): If the left-hand stack is empty: 
      Pop each element off the right-hand stack and 
      push it onto the left-hand stack. This effectively 
      reverses the right-hand stack onto the left-hand stack. 
     Pop and return the top element of the left-hand stack. 

現在，我聲稱的put和get攤銷成本是O(1)，假設我就與空隊列結束。分析很簡單：我總是將put放在右手堆棧上，而get放在左手堆棧上。所以除了If條款外，每個put是push，並且每個get是pop，它們都是O(1)。我不知道我會執行If子句多少次 - 它取決於put s和get s的模式 - 但我知道每個元素只從右側堆棧移動到左側堆棧。所以在n put S的整個序列和n get S上的總成本爲：n push ES，正pop S和N move s，其中一個move是pop後跟一個push：換句話說，2N put S和get s導致2n push es和2n pop s。因此單個put（或get）的攤銷成本爲push和一個pop。

請注意，正是因爲分期付款的複雜性分析（以及「分期付款」與金融的關聯），銀行家隊列才被調用。銀行家隊列是過去常見面試問題的答案，儘管我認爲它現在被認爲是太熟悉了：提出一個隊列，以分攤的O（1）時間實現以下三個操作：

1 ）獲取和刪除隊列的最舊的元件，

2）將一個新元素到隊列，

3）找到當前最大元素的值。

Answer 6

假設您正在嘗試查找未排序數組的第k個最小元素。 排序數組將是O（n logn）。 那麼找到第k個最小的數字就是找到索引，所以O（1）。

由於數組已經排序，我們再也不需要再排序。我們永遠不會遇到最糟糕的情況。

如果我們執行n次嘗試查找第k個最小的查詢，它仍然是O（n logn），因爲它在O（1）上占主導地位。如果我們平均每次操作的時間，它將是：

（n logn）/ n或O（logn）。所以，時間複雜性/操作次數。

這是分期付款的複雜性。

我想，這是怎麼一回事呢，我只是學習它太..