0. 序言
如果你對(duì)簡(jiǎn)單的復(fù)雜度分析不了解鲜锚，請(qǐng)?zhí)D(zhuǎn)閱讀：http://www.reibang.com/p/2d5e5f1bc77e
如果你想看常見的時(shí)間復(fù)雜度實(shí)例分析狈定，請(qǐng)?zhí)D(zhuǎn)閱讀：http://www.reibang.com/p/4c8fa84a9393
閱讀本篇文章，建議先跳轉(zhuǎn)閱讀：http://www.reibang.com/p/08d1d509c5db
如果你對(duì)簡(jiǎn)單的復(fù)雜度分析以及常見的時(shí)間復(fù)雜度以及最好瓜富、最壞鳍咱、平均時(shí)間復(fù)雜度已經(jīng)了解，想對(duì)均攤時(shí)間復(fù)雜度有更多的了解食呻，那么你可以閱讀本篇文章流炕，一定會(huì)讓你有所收獲澎现。
1. 簡(jiǎn)介
均攤時(shí)間復(fù)雜度仅胞，在我看來(lái)，是平均時(shí)間復(fù)雜度的補(bǔ)充剑辫。平均時(shí)間復(fù)雜度只在某些特殊情況下才會(huì)用到干旧，而均攤時(shí)間復(fù)雜度應(yīng)用的場(chǎng)景比它更加特殊、更加有限妹蔽。
2. 應(yīng)用場(chǎng)景
// array 表示一個(gè)長(zhǎng)度為 n 的數(shù)組
// 代碼中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
這段代碼實(shí)現(xiàn)了往數(shù)據(jù)中插入數(shù)據(jù)的功能椎眯。當(dāng)數(shù)組沒(méi)有滿的時(shí)候挠将，直接插入數(shù)據(jù)到數(shù)組中。當(dāng)數(shù)組滿了以后编整，遍歷數(shù)組求和舔稀，將求和之后的sum值放在數(shù)組中的第一位置，然后把count指針指向索引為1的位置掌测，再將新的數(shù)據(jù)插入内贮。
我們看下這段代碼的最好、最壞汞斧、平均時(shí)間復(fù)雜度夜郁。當(dāng)數(shù)組沒(méi)有滿的時(shí)候，直接將數(shù)據(jù)插入數(shù)組中即可粘勒，這是最理想的情況竞端，所以最好時(shí)間復(fù)雜度為O(1)。當(dāng)數(shù)組滿的時(shí)候庙睡，需要遍歷數(shù)組求和事富，把求和后的數(shù)據(jù)插入，這是最壞的情況乘陪，所以最壞情況的時(shí)間復(fù)雜度為O(n)赵颅。
平均時(shí)間復(fù)雜度是多少呢？我們分析下：假設(shè)數(shù)組的長(zhǎng)度是n暂刘，根據(jù)數(shù)據(jù)插入的位置的不同饺谬，我們可以分為n種情況，每種情況的時(shí)間復(fù)雜度是O(1).當(dāng)數(shù)組滿了的時(shí)候插入一個(gè)數(shù)據(jù)谣拣，這個(gè)時(shí)候需要遍歷求和募寨，這個(gè)時(shí)候的時(shí)間復(fù)雜度是O(n)，而n+1種情況發(fā)生的概率一樣森缠，都是1/n+1拔鹰。所以根據(jù)加權(quán)平均計(jì)算法，求得的平均時(shí)間復(fù)雜度是：
以上的O(1)是去掉系數(shù)和常數(shù)得出來(lái)的結(jié)果贵涵。
但是你會(huì)發(fā)現(xiàn)這段代碼平均時(shí)間復(fù)雜度的分析并不需要引入概率列肢。我們對(duì)比下find示例（http://www.reibang.com/p/08d1d509c5db）和以上insert示例，發(fā)現(xiàn)兩者有很大區(qū)別：
① find函數(shù)在極端情況下宾茂，復(fù)雜度才為O(1),但insert在大部分情況下瓷马，時(shí)間復(fù)雜度都為O(1),只有個(gè)別情況下，時(shí)間復(fù)雜度才是O(n).
② insert函數(shù)跨晴，O(1)時(shí)間復(fù)雜度的插入和O(n)時(shí)間復(fù)雜度的插入欧聘，出現(xiàn)的頻率都是有規(guī)律可循的，先是n個(gè)O(1)的插入端盆，然后是O(n)的遍歷求和插入怀骤，接著是1個(gè)O(1)的操作费封，緊跟著是n-1個(gè)O(1)的操作，然后循環(huán)往復(fù)后面三種操作蒋伦。
綜上你會(huì)發(fā)現(xiàn)弓摘，find操作在執(zhí)行的時(shí)候，你并不知道find操作會(huì)執(zhí)行多少次痕届，因?yàn)閿?shù)據(jù)不同衣盾，發(fā)生的find的概率不同，所以用加權(quán)平均時(shí)間復(fù)雜度分析比較合理爷抓，而insert操作在執(zhí)行的時(shí)候势决，因?yàn)橛幸?guī)律可循，所以很多情況下蓝撇，insert執(zhí)行插入的位置的概率是100%的O(1)果复，而只有很少情況是O(n)——針對(duì)大部分執(zhí)行100%概率是低階，很少概率是高階時(shí)間復(fù)雜度的情況渤昌，我們不適合用平均時(shí)間復(fù)雜度去分析虽抄，這個(gè)時(shí)候用均攤時(shí)間復(fù)雜度分析較為合理。
顧名思義：均攤復(fù)雜度独柑，就是把量級(jí)高的操作所耗費(fèi)的時(shí)間分擔(dān)到量級(jí)低的操作上迈窟，看平攤后的量級(jí)是多少。拿上面的例子來(lái)說(shuō)：每次O(n)的遍歷求和操作后面忌栅，會(huì)跟著1次O(1)的插入操作车酣，然后跟著n-1次O(1)的插入操作，所以把耗時(shí)多的遍歷求和操作的時(shí)間均攤到接下來(lái)的n次耗時(shí)少的操作上索绪，也就是平均執(zhí)行2次操作湖员，所以這一組連續(xù)的操作的均攤復(fù)雜度就是O(1)。
綜上：對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作瑞驱，大部分情況下時(shí)間復(fù)雜度都很低娘摔，只有個(gè)別情況下時(shí)間復(fù)雜度比較高，而且這些操作之間存在前后連貫的時(shí)序關(guān)系唤反，這個(gè)時(shí)候凳寺，適合運(yùn)用均攤復(fù)雜度分析代碼，而此時(shí)均攤時(shí)間復(fù)雜度就等于最好情況時(shí)間復(fù)雜度彤侍。
3. 后續(xù)
如果大家喜歡這篇文章肠缨，歡迎點(diǎn)贊！
如果想看更多 數(shù)據(jù)結(jié)構(gòu) 方面的文章拥刻，歡迎關(guān)注!
