今天要介紹最後一種時間複雜度的分析技巧，要是你能夠把這幾天介紹的三種技巧融會貫通，之後在大部分的場景你應該都有辦法看出一段程式的時間複雜度。

之所以說大部分是因為遞迴的時間複雜度分析比較特別一點，不過這不是現在要提的東西

那廢話不多說，讓我們開始最後一項技巧的介紹吧！

均攤分析（Amortized Analysis）

前面兩項技巧的名稱（數迴圈、數學分析）都只是我們自己取的，但均攤分析很明顯有屬於自己的正式名稱，不論是在教科書還是論文中這種作法都被叫做均攤分析（Amortized Analysis），由此應該看得出來它的與眾不同之處。

開始之前先簡單列點介紹一下這種技巧：

• 使用情境：
  • 當某個演算法或資料結構有好幾種不同的操作，而某個操作的時間成本特別大時
  • 當某個演算法或資料結構有的一些操作有好幾種狀態，而當那些操作處於特定狀態時的時間成本會變得特別大

因為前面沒特別提過什麼是資料結構，因此這邊惡補一下XD：所謂資料結構就是透過「某種形式」來存資料，使演算法能節省時間並更高效的利用記憶體。
如陣列就是透過連續的序列來存資料，因此它的特性就是能高效的修改元素，但它的劣勢就是搜尋/刪除元素了。

• 核心概念：
  • 分析那些時間最糟糕的操作，看看能不能證明那些糟糕操作的出現次數不會那麼多，因此整體的平均時間不會像想像的那麼糟糕
  • 目的在求出平均時間，因此可能有時候呼叫某操作會跑特別久，但因為可以證明其他大部分時候都一定會跑很快，因此整體時間沒那麼差
  • 讓時間成本較低的操作去「牽制」時間成本高的操作、或者說將時間成本高的操作的時間能「均攤」到時間成本比較低的操作後取平均時間
  • 分析對象是最糟糕情況下的平均時間，"average time in the worst case"、而非普通的"average time"，所以別和之前 Day 6 講插入排序時提到過的 "average time complexity" 搞混囉！
• 簡單範例：
  • 假設某演算法連續進行 次操作所花費的時間總共是 ，那該演算法的均攤成本就會是

不過其實均攤分析只是一種分析的「策略」，所以就我所知它還能再往下分成三種技巧，分別為：

1. Aggregate analysis（聚集法）
2. The accounting method（記帳法）
3. The potential method（位能法）

雖說分成三種技巧，不過他們比較像是用三種不同的角度來做同一件事情。

以下將分開來介紹這三種技術，不過在此之前要先舉出範例作為等一下展示這些技術時的例子。

堆疊（stack）是一種經典的資料結構，用比喻來說的話它就像一個洋芋片罐，對於這個罐子你只能做兩件事：放洋芋片、拿洋芋片。然後你會發現到你最早放進去的洋芋片會最晚被拿出來，這就是 stack LIFO（Last in, First out）後進先出的特性

想知道更多可以參考 Stack: Intro(簡介)

1. 堆疊操作（stack operation）
   假設一個 stack 有以下三個操作：

   1. PUSH(S, x)：將元素 x 推入堆疊 S 頂端，這是個 操作
   2. POP(S)：將堆疊 S 頂端的一個元素拿走，這是個 操作（如果堆疊 S 已經空了就不能 POP）
   3. MULTIPOP(S, K)：連續地從堆疊 S 中拿走 K 個元素

      while (!S.empty() && k != 0) {
          S.pop();
          --k;
      }
      

      以上是 MULTIPOP 的實作，因此它是個 的操作，因為要不就是連續 pop() K 次；要不就是沒 pop() 滿 K 次結果 stack 就空了。
      請問對於前面的 stack，假設 stack 一開始為空，則連續執行 n 次操作的總時間複雜度是多少？

2. 二進位計數器（incrementing a binary counter）
   一個有 K 個位元的二進位計數器，從 0 開始往上計數， 。
   說的嚴謹一點：存在一個長度為 K 的陣列 A，然後我們有一個操作叫做 increment(A, K) 。
   以下是該計數器的實作：

   void increment(bool A[], int K) {
       int i = 0;
       while (i < K && A[i] == 1) {
           A[i] = 0;
   		++i;
       }
       if (i < K) A[i] = 1;
   }
   
   int main() {
       int K;
       cin >> K;
       // 陣列 A 可以被表示為長度為 K 的 bool 陣列
       bool A[K + 1];
       // 求經過一連串 increment(A, K) 後的時間複雜度
   }
   

   下圖是我們計數器從 0 算到 16 的示意圖

   
   求從 0 開始，經過 n 次 increment 運算後，K 位元的二進位計數器的總時間複雜度為多少？

我隨便算

1. 請問對於前面的 stack，假設 stack 一開始為空，則連續執行 n 次操作的總時間複雜度是多少？
   因為三種操作中，時間複雜度最糟糕的操作是 MULTIPOP，而每次 MULTIPOP 最糟糕會花費 的時間，因此總時間複雜度是

2. 求從 0 開始，經過 n 次 increment 運算後，K 位元的二進位計數器的總時間複雜度為多少？
   最糟糕的情況下，每做一次 increment 需要 的時間（例如：7 + 1 = 8 需要變動 4 個 bit），因此總時間複雜度為

其實上面這樣分析也不能說它不對喔！因為按照 Big O 的定義它是正確的，不過真的有點太悲觀了

Aggregate analysis 聚集分析

直接分析一連串操作的總時間上界 ，然後再計算平均時間

• 從整體來看事情、很豪邁的硬派做法

1. 請問對於前面的 stack，假設 stack 一開始為空，則連續執行 n 次操作的總時間複雜度是多少？

   因為 stack 一開始為空，因此我們可以知道一個東西在 stack 中，放進去後只會被拿出來一次
   所以因為 的次數 ， 的次數 也必成立
   因此有 的次數
   總時間複雜度為 ，平均每個操作為

2. 求從 0 開始，經過 n 次 increment 運算後，K 位元的二進位計數器的總時間複雜度為多少？

   因為很難精準計算每個數字在 increment 時的時間，因此我們可以換個角度來看：
   A[0] 位置的 bit 每 1 次 increment 都會變...總共變 次
   A[1] 位置的 bit 每 2 次 increment 都會變...總共變 次
   A[2] 位置的 bit 每 4 次 increment 都會變...總共變 次
   發現規律之後就可以加總列式了，因為知道 n 個數大概會有 個位元，因此對於每次更新的位元數量和可列式如下：
   
   右邊的無窮等比級數和昨天有算過，因此偷懶套一下結論：
   
   總時間複雜度為 ，平均每個操作為

The accounting method 記帳分析

從金錢記帳的角度來分析複雜度，是一個很有趣也很直覺的分析方法，

它的做法可以想像成有對於每個操作都各有一本銀行帳簿，此時為每一種操作定義不同的「均攤成本」（比一比：聚集分析是把每個操作的成本看作一樣直接加起來分析）。

這種「均攤成本」與真實的成本不一定一樣，有些操作的均攤成本是「操作本身的開銷」+「預付成本」；有些操作的均攤成本為 0。

令 代表第 個操作的真實成本； 第 次運算的均攤成本。

我們設計的成本必須使下式成立：

則總預付成本：

如此一來，我們只要加總所有的均攤成本就能知道總時間複雜度了！

這種分析技巧的原理其實就是前面說的讓時間成本高的操作的時間能「均攤」到時間成本比較低的操作。

因此我們若觀察到某些較耗時的操作的出場頻率會被一些較省時的操作牽制，此時我們就可以將耗時操作的成本設定為 0、省時操作的成本設定為「操作本身的開銷」+「預付成本」，並讓預付成本來支付耗時操作的開銷。

• 讓耗時操作用免費的，時間成本就用省時操作辛辛苦苦存的錢去付包養

1. 請問對於前面的 stack，假設 stack 一開始為空，則連續執行 n 次操作的總時間複雜度是多少？

因為很明顯 POP 和 MULTIPOP 會受到 PUSH 的牽制，因為若堆疊內的元素不夠根本就不能拿東西出來！因此可以如下設計均攤成本：

可以注意到 PUSH 的均攤成本為 2，1 用來支付自己的實際成本，剩下的 1 作為預付成本「存起來」，等到需要 POP 或 MULTIPOP 的時候就用預付成本來支付，因為 MULTIPOP 若能夠拿出 k 個元素，就代表它們在被 PUSH 進來時就有存好自己的預付成本了，因此 MULTIPOP 完全不需要自己支付成本。
這樣的總時間複雜度顯然是 ，平均每個操作為
或者換個角度來看可以直接把它的均攤成本當成平均的操作成本 ，結果一樣。

2. 求從 0 開始，經過 n 次 increment 運算後，K 位元的二進位計數器的總時間複雜度為多少？

首先我們可以觀察到兩件事：(1.) 因為在計數器中是從 0 開始的，因此可以發現位元從 0 變 1 的次數無論何時都會大於等於 1 變 0 的次數，因為 0 要先變 1 才有 1 能變回 0；(2.) 每次 increment 只會恰好產生一次的 0 變 1
根據兩點觀察，我們可以如下設計均攤成本：

讓 0 變 1 的成本變成 2，多出來的 1 作為預付成本來支付之後所需要的 1 變 0。
這樣的總時間複雜度顯然是 ，平均每個操作為
或者換個角度來看可以直接把它的均攤成本當成平均的操作成本 ，結果一樣。

The potential method 位能分析

我個人認為這方法的名稱取的很到位！

在物理學中，位能是物體由於其位置或狀態而儲存的能量。最常見的位能形式有重力位能、電位能等等。
而位能的函數通常被定義成一個僅與位置有關的函數，使得位能轉換所作的功可表達為這兩點位能函數值的差。講白話一點就是：位能升高代表了能量的儲存、位能降低代表了能量的釋放。
那所謂的位能分析就像是在做一台雲霄飛車一樣，你在爬坡時慢慢累積你的位能。而經歷了漫長的位能累積後，在頂端一次釋放，急遽釋放剛才累積的位能

那先直接開始介紹：

• 起初我們資料結構的狀態會用 表示。
• 表示當資料結構 被第 個操作改變後的狀態
• 表示位能函數（potential function），它表示了資料結構 當下某種狀態的數值
• 表示第 個操作的真實成本
• 表示第 個操作的均攤成本，
• 上一點也表示了：
• 根據上一點，只要 ，就代表我們的均攤成本能夠成為實際成本的上界，也因此一般傾向讓

多看幾遍會發現其實位能分析跟記帳分析很像，只不過記帳分析沒有規定均攤成本和實際成本的差該訂多少；而位能分析則明確定義均攤成本就是操作本身的開銷加上該操作對位能的變化量（對資料結構某種「狀態」的改變量）。因此其實可以把位能分析當成更通用的記帳分析。

因為只需要知道該如何定義位能函數，使得某些較省時的操作累積位能、讓耗時操作消耗位能，並證明出均攤開銷為常數就可以了！所以其實在較為複雜的狀況下，位能分析比較實用！在一些較正式的演算法書籍中也是如此。

1. 請問對於前面的 stack，假設 stack 一開始為空，則連續執行 n 次操作的總時間複雜度是多少？

首先將位能函數 定義為 stack 中元素的數量

操作	實際成本		均攤成本
PUSH	1		1+1=2
POP	1		1+(-1)=0
MULTIPOP

因為 PUSH 最多可能呼叫 次，因此這樣的總時間複雜度顯然是 ，平均每個操作為
或者換個角度來看可以直接把它的均攤成本當成平均的操作成本 ，結果一樣。

2. 求從 0 開始，經過 n 次 increment 運算後，K 位元的二進位計數器的總時間複雜度為多少？

首先將位能函數 定義為計數器中 1 的數量；並令 表示第 個 increment 中，從 1 變 0 的位元數。

操作	實際成本		均攤成本
increment

可以注意到因為除了在溢位時實際成本等於 以外，其他時候都會等於 ，因此實際成本一定小於等於

因此平均的操作成本 ，總時間複雜度為

小結

今天的錯誤可能偏多，請各位敬請見諒...若有大神有看到哪邊寫錯的也非常歡迎在留言區指出，謝謝！

今天介紹了均攤分析和其底下的三種分析方法，明天預計會再帶一個均攤分析的案例，請各位敬請期待！