資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學資料結構中的均攤時間複雜度
均攤分析
當偶爾的操作非常慢，但大多數頻繁執行的操作速度很快時，可以使用這種分析方法。在資料結構中，我們需要對雜湊表、不相交集等進行均攤分析。
在雜湊表中，大多數情況下搜尋時間複雜度為 O(1)，但有時會執行 O(n) 次操作。當我們想要搜尋或插入雜湊表中的元素時，大多數情況下是常數時間，但當發生衝突時，需要 O(n) 次操作來解決衝突。
聚合方法
聚合方法用於查詢總成本。如果我們想新增一堆資料，則需要透過以下公式找到均攤成本。
對於 n 個操作的序列，成本為：
$\frac{Cost ( n\:operations)}{n}=\frac{Cost (normal\:operations)+Cost (Expensive\:operations)}{n}$
均攤分析示例
對於動態陣列，可以在給定索引處以 O(1) 的時間插入項。但是，如果陣列中不存在該索引，則它無法在常數時間內執行任務。在這種情況下，它首先將陣列大小加倍，然後在索引存在時插入元素。
對於動態陣列，設 ci 為第 i 次插入的成本。
$So\:ci=1+\begin{cases}i\:-\:1,if\:i-1\:is\:power\:of\:2 \0, \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:Otherwise\end{cases}$
$$\frac{\displaystyle\sum\limits_{i=1}^n ci}{n}\leq\frac{n+\displaystyle\sum\limits_{j=1}^{\lfloor\log{2}{\lgroup n-1\rgroup}\rfloor} 2j}{n}=\frac{O\lgroup n\rgroup}{n}$$
更新於：2019年8月27日
895 次瀏覽
廣告