常用的大Ο大Θ大Ω就不说了，一般知道大Ο也就行了。这里主要说说补偿分析法（amortized analysis），有的翻译成均（平）摊分析。英文单词amortized的意思是分期付款，这个比较容易理解。在数据结构中的应用例子有移至前端的自组织线性表，自适应树等。
在一些应用中，数据结构是从属于一系列操作而不是一个操作的，这时，我们分析最坏的情况时就不能分析每一个操作的最坏情况，然后认为整个操作序列的最坏情况就是单个最坏情况的和。
最简单的例子是二进制计数器。假设一个从0开始的n位计数器。用数组A[0…n-1]来表示，A[0]存最低位。对它加1的算法如下：
Increment(A){
for(i=0;i<n && A[i]==1);i++)
A[i]=0;
if(i<n)
A[i]=1;
}
即从最低位开始，遇到1就把它变成0，继续把进位往上送，直到遇到0。如果从0到n－1位都是1，就不用把第n－1位改成1了。
这个算法没有什么，我们一般比较关心最坏的情况。如果孤立的分析一次加1操作，那么它的最坏情况是需要O(n)的时间复杂度。那么对m次操作它的最坏情况是不是O(m*n)呢？这要看这m次操作是否有关系，如果这m此操作都是没有任何关系的，也就是说第一次加1时，A[0…n-1]的值是随机的，第二次加1时A[0…n-1]还是随机的，那么最坏可能是O(m*n)。现在考虑的条件是：每次加1都是在前一次的结果的基础上加1的，比如初值为0000（n＝4），第一次加1后变成0001，第二次加1是加在0001上的使它变成0010。这样的话我们就会发现前面的分析方法把事情看得太糟糕了。在每次都加在上次的结果上时，不可能每次都要O(n)的复杂度。比如某次加1使得计数器进行n次变化使得计数器变成0000，那么下次只有1次变化。
因此我们可以把这一序列操作看成一个整体，求出所有的操作的复杂度然后除以m。为了简便，我们假设从0开始计数，共计数m＝2n次，（从00…00到11..11）。
我们来分析第0位，000000，000001,000010,000011,…….
发现每2（隔一）个数变化一次，类似的第1位每4个数变化一次，……
所以第i位变化m/2i次，0<=i<=n-1
所有的变化次数为：
所以一次操作的代价为O（1）。
这种方法在《算法导论》被称为聚聚方法。它的思路是：寻找这m个相互有关联的操作的总代价的上界T(m)，每个操作的平均为T(m)/m。
这种方法的适用场合是：这m个操作的总代价比较容易求。但有时候我们根本不知道具体的操作到底是什么。比如移至前端的自组织线性表。我们根本不知道m次操作会访问哪些数据。
这个问题是：为了提高链表的查询速度，“用最近的过去预测最近的将来”，把最近访问过的元素提到表头，这样如果下次再访问这个数据，就很快可以找到。你可能和我一样担心会不会“万一放到表头的元素都不再或很少再次被访问”，那把它提到表头不但徒劳无功，而且使下一个被访问的元素（如果它在原链表中的位置在被提到表头的元素之前）后退了一个位置？
假设一共进行了m次查询，但不知道每次到底查询哪个数据。那怎么计算复杂性呢？比如，m次都访问某一个元素ai，则一共需要（i+m-1），若m>n，则（i+m-1）/m<(n+m-1)/m<2。比较糟糕的情况是访问顺序是an an-1 ……a1 。则每次访问都要比较n次。可见m次操作的复杂性与每次操作有关。那我们怎么评价把最近访问过的数据移到表头是好是坏呢？我们可能希望把它和“最好的”链表比较。“最好的”链表是什么样子的呢？当然如果每次访问的数据都在表头那就太好了，但我们没法知道下一次访问哪个元素，否则把它移到表头就可以了。有n个元素的链表，有n！种不同的排列。对每一种访问序列，都至少有一个是最好的。
比如访问序列是a1 a1 …….a1 a1 ，最好的链表之一是a1 a2 ……. an 。我们发现如果链表不是动态的，则最好的链表应该是把访问次数最多的放在前面，访问次数少的放后面。证明也很容易，使用不等式 逆序和<乱序和<顺序和 即可。
如果我们知道每个元素的访问次数的话，就可以构造这样一个链表，可惜元素的访问次数我们也是不知道的。也就是说不同的访问序列有不同的“最好的”链表。我们能不能得到一个链表，不论访问序列是什么，我这个链表的访问效率都不比这个访问序列的“最好的”链表相差太多呢（什么叫相差不太多？他们的大O相同？）？显然这个链表必须是动态的，否则我们假设链表的最后一个元素是an ，访问序列为an an …… an an ，则它要O(n)，而“最好的”是O(1)。
事实上，把最近访问过的元素移动表头不会比“最好的”差很多，它最多是“最好的”链表的2倍的时间复杂度。证明稍后再说，怎么理解它不会差太多呢？万一它要差很多呢？另外你（提出这种数据结构的人）是怎么想到要把刚访问的元素移到表头而不是表尾呢？不移到表头而只是前移一个元素会怎么样呢？
先看看在“最好的”链表（正式的名字叫“最优静态排序的链表”，打起来好费劲）中查找一个元素需要比较元素的次数。在“最好的”链表中除了要比较即将访问的元素外，还要比较排在它前面的（也就是访问频率大于等于它的）元素，这些比较即使在“最好的”链表中也是必不可少的。如果我们要找的那个不比“最好的”差很多的链表在访问这个元素时比较了访问频率大于等于它的元素时，我们不用理睬了，因为“最好的”链表也是要比较的。我们期望比较频率比它少的元素的次数不要太多。移到表头方法能帮我们达到这个目标吗？
先考虑只有两个元素a和b的链表。设a的访问频率是i次，b是j次，且i>j 。则在“最好的”链表中访问b时必须比较a（共计j次），现在只考虑在移到表头链表中访问a时需要比较b（这些多余的比较是我们不想要的）的次数。如果某次访问a时a已经在表头了，那么没有多余的比较；只有在访问a时b在表头有多余的比较。假设现在访问的是a，如果上次访问的是a，则a已经在上次被移到了表头了，这次没有多余的比较；如果上次访问的是b，才会有多余的比较。因此“最坏的”情况是访问序列中a的前面都是b，但由于b的个数j比a的个数i少，所以最多有j次多余的比较。而必须的比较是i（比较a）+j（比较b）+j（“最好的”链表中必不可少的多余比较）＝i+2j次；移动表头链表的最坏的时候需要比较i+j+j+j<2(i+2j)。多个元素的分析和两个类似。
怎么从直观来理解为什么要移到表头呢？把a移到表头就可以避免下次访问a时再访问b；但如果下次访问b的话就会产生一次多余的比较。可以说是有利有弊，其中如果a的访问概率大的话则利多弊少。比如我们假设如果a移到表头，下次访问a则得“利”1，若下次访问b则得“利”－1。那么得“利”的数学期望是1*i/(i+j)+(-1) *j/(i+j)>0。那么把b移到表头呢？若下次访问b当然很好。若下次访问a呢？因为在“最好的”链表中访问b是访问a都是必不可少的，那么移到表头算法也不算太坏（反正大家都要比较）。
说了半天，和补偿分析法似乎没有任何关系。我们再来看一个和动态链表比较类似的问题――自适应树。
在一个平衡的BST中，访问一个节点最多要O（log(n)）的时间复杂度，但如果不是平衡的BST那么可能最坏要O（n）。如果知道每个节点的访问频率，那么和链表类似可以得到一个最佳BST。不过最佳BST的构造要比最优静态排序的链表困难的多。简单的把频率最大的节点当成根是不行的，因为为了保持BST的数据结构，可能把频率较大的很多节点都放到层次较大的地方去了，反而使总的代价变大。构造最佳BST的方法等到动态规划算法再说吧。
类比链表，我们也想构造一个动态的BST，使得不论什么样的访问序列，这个动态BST的访问效率都不比这个访问序列的最佳BST差很多。“把刚访问的节点移动到根”――这是我的第一感觉。当然，直接移动到根是不行的，这个树就不是BST了。移动的过程还要保持BST的数据结构。采用AVL树的旋转方法可以帮我们做到这点。那么m