Data Structures公開課聽課筆記--序

按道理講我是沒有這麼高產的，而且這門課實際上我只是剛剛半個小時前聽完了第一周，就是之前提過的UCSD編程系列裡的第二門：datastructure，第一門是algorithm

我只是在半個小時前剛聽完第一周的課，內容很簡單，只是覺得有些有趣，所以先分享一下吧。

第一周：Basic Data Structures

第一周主要介紹了數組，鏈表，單鏈表，樹，樹的遍歷，動態數組的基本概念，這些我覺得就沒有必要分享了，隨便貼幾張圖吧。

單鏈表&雙鏈表的比較（with tail是指鏈表維護一個指向鏈表尾部的指針）

接下來就是我要分享的比較有意思的部分。

amotized analysis，複雜度的分攤分析，就是譬如動態數組的插入這種沒有辦法直觀的計算複雜度的操作（因為有時是常規的插入，有時則需要重新分配內存），我們應該怎樣計算它的複雜度。其實並不難，只是比較有趣。

A、不可避免的介紹

首先我們的動態數組是，每次容量用盡時，就將數組的容量翻倍。

對於這個動態數組，每次插入的花費有兩種情況，第一種是容量夠用，我們只需要存儲新的元素。

第二種是容量不夠用，我們需要創建一個新的二倍的數組，並且把所有元素移動進去，再存儲新的元素。

B、amotized analysis第一種方法，aggregate method，統計分析

統計分析就是如下的公式，把n次操作的花費求和取平均值，求平均複雜度。

C、amotized analysis第二種方法，banker method，銀行演算法

對動態數組的插入來說，大部分插入操作是不需要重新分配內存的，是廉價的操作。而少部分操作是需要重新分配的，是複雜的操作。如果需要分析它的複雜度，我們可以試著想像

在每次廉價的操作時存儲額外的費用，相當於存款，來支付複雜操作的費用。

在動態數組這個例子里，我們假設一次基本操作的費用為1個硬幣，當我們插入了一個下標為n的元素時

首先，我們要花費第一個硬幣，做為基本的插入操作時。

然後我們還要存儲第二個硬幣，作為新插入的n在重新分配內存時移動它的費用。

最後我們要存儲第三個硬幣，做為下標為n/2的元素重新分配內存時移動它的費用。

前兩個很好理解，第三個硬幣可能比較難理解。

之所以要這樣做，是因為每次重新分配內存時，所有的元素之前存儲的第二個硬幣就會被消耗掉，假設新的數組大小為n，那麼坐標小於n/2的那些元素是沒有存儲硬幣作為重新分配內存時的花費的。

而如果每次重新插入元素時都在n/2處存儲第3個硬幣，那麼當數組元素到達n需要重新分配內存時，原來的下標小於n/2的元素也全部都已經有了一個硬幣。

這樣來計算，每次操作最多付出三個硬幣，因此每次操作複雜度最大為3，常數級別。

舉個例子，從大小為1的數組開始插入：

1、首先插入1，插入本身花費1枚硬幣，並且在1上存儲了1枚硬幣，1/2＝0，所以沒有第三枚硬幣

2、插入2，數組的容量不夠，於是數組容量翻倍變為2，把1移動到新數組，花費掉了之前存儲在1上的硬幣。

插入2本身花費1枚硬幣，在2上存儲1枚硬幣，2/2=1，因此在1上存儲1枚硬幣。

3、插入3，數組容量不夠，於是數組容量翻倍變為4，把1，2移動到新數組，花費掉了之前存儲在1，2上的硬幣。

插入3本身花費1枚硬幣，在3上存儲1枚硬幣 ，3/2=1，因此在1上存儲1枚硬幣

4、插入4，數組容量足夠，插入4本身花費1枚，4上存儲1枚，4/2=2，因此在2上存儲1枚。

5、插入5，數組容量翻倍，移動1，2，3，4，花費掉之前在1，2，3，4上存儲的硬幣。。。。。

amotized analysis第三種方法，physicist method，物理學方法

這是個很有意思的計算方法，從物理學勢能的角度來理解，例如物體在不同的高度，就有不同的重力勢能。

從這個角度理解，動態數組經過插入或者刪除操作後會處於不同的狀態，不同的狀態有不同的勢能。

如上圖，這很物理。每次插入的花費為：本次操作的花費+當前狀態的勢能-之前狀態的勢能

對動態數組來說，它的勢能是，2倍的數組大小-數組容量。

數組大小是數組中實際元素的個數

數組容量是數組的實際容量

普通的插入，我們的花費是3，推導過程比較簡單，如下圖

對於需要重新分配內存的插入，我們的花費也是3

當然每次翻倍的動態數組插入操作的複雜度就是常數級別了，但是後面兩種方法的思想還是很有意思的。

推薦閱讀：