在平摊分析(amortized analysis)中，会通过求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。这样就可以说明一个操作的平均代价是很低的，即使序列中某个单一操作的代价很高。平摊分析不同于平均情况分析，它并不涉及概率，它可以保证最坏情况下每个操作的平均性能。
在平摊分析中，赋予对象的费用仅仅是用来分析而已，不需要也不应该出现在程序中。通过做平摊分析，通常可以获得对某种特定数据结构的认识，这种认识有助于优化设计。
利用聚集分析，会证明对所有n，一个n个操作的序列最坏情况下花费的总时间为T(n)。因此，在最坏情况下，每个操作的平均代价，或平摊代价为T(n)/n。注意，此平摊代价是适用于每个操作的，即使序列中有多种类型的操作也是如此。本博客中在后面的章节里，将要讨论另外两种方法——记账方法和势能方法，对不同类型的操作可能赋予不同的平摊代价。
1、PUSH(S,x)：将对象x压入栈S中。
2、POP(S)：将栈S的栈顶对象弹出，并返回该对象。对空栈调用POP会产生一个错误。
现在增加一个新的栈操作MULTIPOP(S,k)，它删除栈S栈顶的k个对象，如果栈中对象数少于k，则将整个栈的内容都弹出。假定k是正整数，否则MULTIPOP会保持栈不变。在下面的伪代码中，STACK-EMPTY在当前栈中没有任何对象时返回TRUE，否则返回FALSE。
下图给出了MULTIPOP的一个例子：
对栈S进行MIULTIPOP操作，栈的初始格局如a。通过MULTIPOP(S,4)弹出栈顶4个对象，结果如b。因为栈中剩下的对象不足7个，下一个操作MULTIPOP(S,7)将栈清空，如c。
在一个包含s个对象的栈上执行MULTIPOP(S,k)操作的运行时间与实际执行的POP操作的次数呈线性关系，因此可以用PUSH和POP操作的抽象代价1来分析描述MULTIPOP的代价。while循环执行的次数等于从栈中弹出的对象数，等于min(s,k)。每个循环步调用一次POP(第3行)。因此，MULTIPOP的总代价为min(s,k)，而真正的运行时间为此代价的线性函数。
下面分析由n个PUSH、POP和MULTIPOP组成的操作序列在一个空栈上的执行情况。序列中一个MULTIPOP操作的最坏情况代价为O(n)，因为栈的大小最大为n。因此，任意一个栈操作的最坏情况时间为O(n)，从而一个n个操作的序列的最坏情况代价为O(n2)，因为序列可能包含O(n)个MULTIPOP操作，每个的执行代价为O(n)。虽然这个分析是正确的，但通过单独分析每个操作的最坏情况代价得到的操作序列的最坏情况时间O(n2)，这显然不是一个确界。
通过使用聚集分析，考虑整个序列的n个操作，可以得到更准确的上界。实际上，虽然一个单独的MULTIPOP操作可能代价很高，但在一个空栈上执行n个PUSH、POP和MULTIPOP的操作序列，代价至多是O(n)，因为当将一个对象压入栈后，至多将其弹出一次。因此，对一个非空的栈，可以执行的POP操作的次数(包括了MULTIPOP中调用POP的次数)最多与PUSH操作的次数相当，即最多n次。因此，对任意的n值，任意一个由n个PUSH、POP和MULTIPOP组成的操作序列，最多花费O(n)时间。一个操作的平均时间为O(n)/n=O(1)。在聚集分析中，将每个操作的平摊代价设定为平均代价。因此，在此例中，所有三种栈操作的平摊代价都是O(1)。
虽然已经证明一个栈操作的平均代价，也就是平均运行时间为O(1)，但并未使用概率分析。实际上得出的是一个n个操作的序列的最坏情况运行时间O(n)，再除以n得到了每个操作的平均代价，或者说平摊代价。
初始时x=0，因此对所有i=0,1,…,k-1，A[i]=0。为了将1(模2k)加到计数器的值上，使用如下过程：
上图显示了将一个8位的二进制计数器递增16次的情况，初始值为0，最终变为16。发生翻转而取得下一个值的位加了阴影。右边给出了位翻转所需的运行代价。注意总代价始终不超过INCREMENT操作总次数的2倍。
当每次开始执行第3-5行的while循环时，希望将1加在第i位上。如果A[i]=1，那么加1操作会将第i位翻转为0，并产生一个进位——在下一步循环迭代时将1加到第i+1位上。否则，循环结束，此时若有i<k，则有A[i]=0，因此第7行将1加到第i位上——将第i位翻转为1。每次INCREMENT操作的代价与翻转的二进制位的数目呈线性关系。
与【1.1 栈操作】一节中的栈操作的例子类似，对此算法的运行时间进行粗略的分析会得到一个正确但不紧的界。最坏情况下INCREMENT执行一次花费Θ(k)时间，最坏情况是——当数组A所有位都为1。因此，对初值为0的计数器执行n个INCREMENT操作最坏情况下花费O(nk)时间。
对于n个INCREMENT操作组成的序列，可以得到一个更紧的界——最坏情况下代价为O(n)，因为不可能每次INCREMENT操作都翻转所有的二进制位。每次调用INCREMENT时A[0]确实都会翻转。而下一位A[1]，则只是每两次调用翻转一次，这样，对一个初值为0的计数器执行一个n个INCREMENT操作的序列，只会使A[1]翻转⌊n/2⌋次。类似地，A[2]每4次调用才翻转一次，即执行一个n个INCREMENT操作的序列的过程中翻转⌊n/4⌋次。一般地，对一个初值为0的计数器，在执行一个由n个INCREMENT操作组成的序列的过程中，A[i]会翻转⌊n/2i⌋次，其中i=0,1,…,k-1。对i≥k，A[i]不存在，因此也就不会翻转。因此，由公式：
知，在执行INCREMENT序列的过程中进行的翻转操作的总数为：
用记账方法(accounting method)进行平摊分析时，会对不同操作赋予不同费用，赋予某些操作的费用可能多于或少于其实际代价。将赋予一个操作的费用称为它的平摊代价：
1、当一个操作的平摊代价超出其实际代价时，将差额存入数据结构中的特定对象，存入的差额称为信用。
2、对于后续操作中平摊代价小于实际代价的情况，信用可以用来支付差额。
将一个操作的平摊代价分解为其实际代价和信用(存入的或用掉的)。不同于聚集分析中所有操作都赋予相同平摊代价的方式，在记账方法中的不同操作可能有不同的平摊代价，必须小心地选择操作的平摊代价。如果希望通过分析平摊代价来证明每个操作的平均代价的最坏情况很小，就应确保操作序列的总平摊代价给出了序列总真实代价的上界。而且，与聚集分析一样，这种关系必须对所有操作序列都成立。如果用ci表示第i个操作的真实代价，用：
表示其平摊代价，则对任意n个操作的序列，要求：
数据结构中存储的信用恰好等于总平摊代价与总实际代价的差值，即：
由上上一张图片中的不等式可知，数据结构所关联的信用必须一直为非负值。如果在某个步骤允许信用为负值，那么当时的总平摊代价就会低于总实际代价，对于到那个时刻为止的操作序列，总平摊代价就不再是总实际代价的上界了。因此必须注意保持数据结构中的总信用永远为非负值。
在【1.1 栈操作】一节中，各个栈操作的实际代价为：
其中k是提供给MULTIPOP的参数，s是调用MULTIPOP时栈的规模。现在为这些操作赋予如下平摊代价：
这里MULTIPOP的平摊代价是常数0，而其实际代价是变量。在此例中，所有三个平摊代价都是常数。一般来说，所考虑的操作的平摊代价可能各不相同，渐近性也可能不同。
下面将通过一个例子证明——通过按平摊代价缴费，可以支付任意的栈操作序列的实际代价。
假定使用1美元来表示一个单位的代价，从一个空栈开始，当将一个盘子放在一叠盘子的最上面，用1美元支付压栈操作的实际代价，将剩余的1美元存为信用(共缴费2美元)。在任何时间点，栈中的每个盘子都存储了与之对应的1美元的信用。每个盘子存储的1美元，实际上是作为将来它被弹出栈时代价的预付费。当执行一个POP操作时，并不缴纳任何费用，而是使用存储在栈中的信用来支付其实际代价。为了弹出一个盘子，取出此盘子的1美元的信用来支付POP操作的实际代价。因此，通过为PUSH操作多缴一点费，可以在POP时不缴纳任何费用。对于MULTIPOP操作，也可以不缴纳任何费用。为了弹出第一个盘子，将其1美元信用取出来支付此POP操作的实际代价。为了弹出第二个盘子，再次取出盘子的1美元信用来支付此POP操作的实际代价，依此类推。因此，预付的费用总是足够支付MULTIPOP操作的代价。换句话说，由于栈中的每个盘子都存有1美元的信用，而栈中的盘子数始终是非负的，因此可以保证信用值也总是非负的。因此，对任意由n个PUSH、POP、MULTIPOP操作组成的序列，总平摊代价为总实际代价的上界。由于总平摊代价为O(n)，因此总实际代价也是O(n)，只是二者的最高项的系数不同而已。
下面使用记账方法再次分析在一个从0开始的二进制计数器上执行INCREMENT操作的平摊代价。由于此操作的运行时间与翻转的位数成正比，因此将翻转的位数作为操作的代价，再次使用1美元表示一个单位的代价。
在平摊分析中，对一次置位操作，设其平摊代价为2美元。当进行置位时，用1美元支付置位操作的实际代价，并将另外1美元存为信用，用来支付将来复位操作的代价。在任何时刻，计数器中任何为1的位都存有1美元的信用，这样对于复位操作，就无需缴纳任何费用，使用存储的1美元信用即可支付复位操作的代价。
现在可以确定INCREMENT的平摊代价。while循环中复位操作的代价用该位储存的1美元来支付。INCREMENT过程至多置位一次(第7行)，因此，其平摊代价最多为2美元。计数器中1的个数永远不会为负，因此，任何时刻信用值都是非负的。所以，对于n个INCREMENT操作，总平摊代价为O(n)，为总实际代价的上界。
势能方法平摊分析并不将预付代价表示为数据结构中特定对象的信用，而是表示为“势能”，或简称“势”，将势能释放即可用来支付未来操作的代价，将势能与整个数据结构而不是特定对象相关联。势能方法工作方式如下。
将对一个初始数据结构D0执行n个操作。对每个i=1,2,…,n，令ci为第i个操作的实际代价，令Di为在数据结构Di-1上执行第i个操作得到的结果数据结构。势函数Φ将每个数据结构Di映射到一个实数Φ(Di)，此值即为关联到数据结构Di的势。第i个操作的平摊代价
用势函数定义为：
记上式为公式A。每个操作的平摊代价等于其实际代价加上此操作引起的势能变化。由公式A可得n个操作的总平摊代价为：
记上式为公式B。公式B的第二个等式是根据：
推导出来的。如果能定义一个势函数Φ，使得Φ(Dn)≥Φ(D0)，则总平摊代价：
给出了总实际代价：
的一个上界。实际中，不是总能知道将要执行多少个操作。因此，如果对所有i，要求Φ(Di)≥Φ(D0)，则可以像记账方法一样保证总能提前支付。通常将Φ(D0)简单定义为0，然后说明对所有i，有Φ(Di)≥0。直觉上，如果第i个操作的势差Φ(Di)-Φ(Di-1)是正的，则平摊代价：
表示第i个操作多付费了，数据结构的势增加。如果势差为负，则平摊代价表示第i个操作少付费了，势减少用于支付操作的实际代价。
公式A和公式B定义的平摊代价依赖于势函数的选择。不同的势函数会产生不同的平摊代价，但平摊代价仍为实际代价的上界。在选择势函数时，可以做出一定的权衡，是否使用最佳势函数依赖于对时间界的要求。
为了展示势能方法，再次回到栈操作PUSH、POP和MULTIPOP的例子，将一个栈的势函数定义为其中的对象数量。对于初始的空栈D0，有Φ(D0)=0。由于栈中对象数目永远不可能为负，因此，第i步操作得到的栈Di具有非负的势，即：
因此，用Φ定义的n个操作的总平摊代价即为实际代价的一个上界。下面计算不同栈操作的平摊代价。如果第i个操作是PUSH操作，此时栈中包含s个对象，则势差为：
则由公式A，即：
得到PUSH操作的平摊代价为：
上式中根据下图ci=1。
假设第i个操作是MULTIPOP(S,k)，将k’=min(k,s)个对象弹出栈。对象的实际代价为k’，势差为：
因此，MULTIPOP的平摊代价为：
类似地，普通POP操作的平摊代价也为0。
每个操作的平摊代价都是O(1)，因此，n个操作的总平摊代价为O(n)。由于已经论证了Φ(Di)≥Φ(D0)，因此，n个操作的总平摊代价为总实际代价的上界。所以n个操作的最坏情况时间为O(n)。
作为势能方法的另一个例子，本节再次分析二进制计数器递增问题。将计数器执行i次INCREMENT操作后的势定义为bi=i次操作后计数器中1的个数。
下面计算INCREMENT操作的平摊代价。
假设第i个INCREMENT操作将ti个位复位，则其实际代价ci至多为ti+1，因为除了复位ti个位之外，还至多置位1位。如果bi=0，则第i个操作将所有k位都复位了，因此bi-1=ti=k。如果bi>0，则bi=bi-1-ti+1。无论哪种情况，都有：bi≤bi-1-ti+1，势差为：
因此，平摊代价为：
如果计数器从0开始，则Φ(D0)=0。由于对所有i均有Φ(Di)≥0，因此，一个由n个INCREMENT操作构成的序列的总平摊代价是总实际代价的上界，所以n个INCREMENT操作的最坏情况时间为O(n)。势能方法给出了分析计数器问题的一个简单方法，即使计数器不是从0开始也可以分析。计数器初始时包含b0个1，经过n个INCREMENT操作后包含bn个1，其中0≤b0,bn≤k，其中k是计数器二进制位的数目。于是可以将公式：
改写为：
对所有1≤i≤n，有：
由于Φ(D0)=b0且Φ(Dn)=bn，n个INCREMENT操作的总实际代价为：
由于b0≤k，因此只要k=O(n)，总实际代价就是O(n)。换句话说，如果至少执行n=Ω(k)个INCREMENT操作，不管计数器初值是什么，总实际代价都是O(n)。
对某些应用程序，可能无法预先知道它会将多少个对象存储在表中。为一个表分配一定的内存空间，随后可能会发现不够用。于是必须为其重新分配更大的空间，并将所有对象从原表中复制到新的空间中。类似地，如果从表中删除了很多对象，可能为其重新分配一个更小的内存空间就是值得的。本节研究动态扩张和收缩表的问题，将使用平摊分析证明，虽然插入和删除操作可能会引起扩张或收缩，从而有较高的实际代价，但它们的平摊代价都是O(1)。而且，将讨论如何保证动态表中的空闲空间相对于总空间的比例永远不超过一个常量分数。
假定动态表支持TABLE-INSERT和TABLE-DELETE操作：
1、TABLE-INSERT将一个数据项插入表中，它占用一个槽(slot)，即保存一个数据项的空间。
2、TABLE-DELETE从表中删除一个数据项，从而释放一个槽。
用于组织动态表的数据结构可以使用栈、堆或者散列表，也可以使用数组或数组集来实现对象的存储。将一个非空表T的装载因子α(T)定义为表中存储的数据项的数量除以表的规模(槽的数量)。赋予空表(没有数据项)的规模为0，并将其装载因子定义为1。如果一个动态表的装载因子被限定在一个常量之下，则其空闲空间相对于总空间的比例永远也不会超过一个常数。
首先分析只允许插入数据项的情况，然后考虑既允许插入也允许删除的一般情况。
假定表的存储空间是一个槽的数组。当所有槽都已被使用时，表被填满，此时装载因子为1。在某些软件环境中，当试图向一个满的表插入一个数据项时，唯一的选择是报错退出。但假定软件环境与很多现代软件系统一样，提供了一个内存管理系统，可以根据要求分配和释放内存块。因此，当试图向一个满的表插入一个数据项时，可以扩张表——分配一个包含更多槽的新表。由于总是需要表位于连续的内存空间中，因此必须为更大的新表分配一个新的数组，然后将数据项从旧表复制到新表中。
一个常用的分配新表的启发式策略是：为新表分配2倍于旧表的槽。如果只允许插入操作，那么装载因子总是保持在1/2以上，因此，浪费的空间永远不会超过总空间的一半。
此处有两个“插入”过程：TABLE-INSERT自身及第7行和第11行的基本插入(elementary insertion)过程。可以将每次基本插入操作的代价设定为1，然后用基本插入操作的次数来描述TABLE-INSERT的运行时间。假定TABLE-INSERT的实际运行时间与插入数据项的时间呈线性关系，即第3行分配初始表的开销为常量，而第6行和第8行分配与释放内存空间的开销是由第7行的数据复制代价决定的。称第6-10行执行了一次扩张动作。
下面分析对一个空表执行n个TABLE-INSERT操作的代价。第i个操作的代价ci是怎样的呢？如果当前的表有空间容纳新的数据项(或者这是第一个插入操作)，则ci=1，因为只需执行一次基本插入操作(第11行)。但如果当前表满，会发生一次扩张，则ci=i：第11行基本插入操作的代价为1，再加上第7行将数据项从旧表复制到新表的代价i-1。如果执行n个操作，一个操作的最坏情况时间为O(n)，从而可得n个操作总运行时间的上界O(n2)。O(n2)并不是一个紧确界，因为在执行n个TABLE-INSERT操作的过程中，扩张操作其实是很少的。具体地说，仅当i-1恰为2的幂时，第i个操作才会引起一次扩张。一次插入操作的平摊代价实际上是O(1)，可以用聚集分析来证明这一点。第i个操作的代价为：
因此，n个TABLE-INSERT操作的总代价为：
由于包含至多n个代价为1的操作，而其他操作的代价形成一个等比数列，所以得到了上述结果。由于n个TABLE-INSERT操作的总代价以3n为上界，因此，单一操作的平摊代价至多为3。
直观上，处理每个数据项要付出3次基本插入操作的代价：将它插入当前表中，当表扩张时移动它，当表扩张时移动另一个已经移动过一次的数据项。如假定表的规模在一次扩张后变为m，则表中保存了m/2个数据项，且它当前没有储存任何信用。现在为每次插入操作付3美元，立刻发生的基本插入操作花去1美元，将另外1美元储存起来作为插入数据项的信用，将最后1美元储存起来作为已在表中的m/2个数据项中某一个的信用；当表中保存了m个数据项已满时，每个数据项都储存了1美元，用于支付扩张时基本插入操作的代价。
也可以用势能方法来分析n个TABLE-INSERT操作的序列，定义一个势函数，要求：
1、在扩张操作之后其值为0；
2、表满时其值为表的规模。
可将势函数定义为：
可以满足上述两点要求：
为了分析第i个TABLE-INSERT操作的平摊代价，令numi表示第i个操作后表中数据项的数量，sizei表示第i个操作后表的总规模，Φi表示第i个操作后的势。初始时有num0=0，size0=0及Φ0=0，然后：
1、如果第i个TABLE-INSERT操作没有触发扩张，那么有sizei=sizei-1，此操作的平摊代价为：
2、如果第i个TABLE-INSERT操作触发了一次扩张，则有sizei=2·sizei-1及sizei-1=numi-1=numi-1，这意味着sizei=2·(numi-1)。因此，此操作的平摊代价为：
下图画出了numi、sizei和Φi随i变化的情况。看图时注意势是如何累积来支付表扩张代价的：
上图描述了在执行n个TABLE-INSERT操作的过程中，表中数据项数量numi、表规模sizei及势Φi=2·numi-sizei的变化，每个值都是在第i个操作后测量的。细线显示了numi的变化，虚线显示了sizei的变化，粗线显示了Φi的变化。注意，在一次扩张前，势变为表中数据项的数量，因此可以用来支付将所有数据项移动到新表所需的代价。而扩张之后，势变为0，但会立即变为2——引起扩张的那个数据项被插入表中。
TABLE-DELETE操作中将指定数据项从表中删除是很简单的。但为了限制浪费的空间，可以在装载因子变得太小时对表进行收缩操作。表收缩与表扩张是类似的操作：当表中的数据项数量下降得太少时，分配一个新的更小的表，然后将数据项从旧表复制到新表中。之后可以释放旧表占用的内存空间，将其归还给内存管理系统。理想情况下，希望保持两个性质：
1、动态表的装载因子有一个正的常数的下界。
2、一个表操作的平摊代价有一个常数上界。
假定用基本插入、删除操作的次数来衡量动态表操作的代价。
既然当插入一个数据项到满表时应该将表规模加倍，那么假设策略A为：当删除一个数据项导致表空间利用率不到一半时就将表规模减半。策略A可以保证表的装载因子永远不会低于1/2，但遗憾的是，这样可能会导致操作的平摊代价过大。
插入、删除、删除、插入、插入、删除、删除、插入、插入…
第一个插入操作导致表规模扩张至n。接下来两个删除操作导致表规模收缩至n/2。接下来两个插入操作引起另一次扩张，依此类推…每次扩张和收缩的代价为Θ(n)，而收缩和扩张的次数为Θ(n)。因此，n个操作的总代价为Θ(n2)，使得每个操作的平摊代价为Θ(n)。
策略A的缺点是很明显的：
1、在表扩张之后，无法删除足够多的数据项来为收缩操作支付费用；
2、在表收缩之后，无法插入足够多的数据项来为扩张操作支付费用。
可以改进上述策略A——允许表的装载因子低于1/2。当向一个满表插入一个新数据项时，仍然将表规模加倍，但只有当装载因子小于1/4而不是1/2时，才将表规模减半。因此装载因子的下界为1/4。
直观来看可能装载因子为1/2比较理想，而表的势此时应该为0。随着装载因子偏离1/2，势应该增长，使得当扩张或收缩表时，表已经储存了足够的势来支付复制所有数据项至新表的代价。因此需要这样一个势函数：
2、表扩张或收缩之后，装载因子重新变为1/2，而表的势降回0。
观察到空表的势为0，且势永远不可能为负。因此，用势函数定义的操作序列的总平摊代价是总实际代价的上界。下下一张图是在执行n个TABLE-INSERT和TABLE-DELETE操作的过程中，表中数据项数量numi、表规模sizei及势Φi的变化情况，每个值都是在第i个操作后测量得到的，其中Φi的定义如下：
下图中的细线显示了numi的变化，虚线显示了sizei的变化，粗线显示了Φi的变化。注意，在一次扩张前，势累积到了表中数据项的数量，因此可以用来支付扩张过程中数据项移动的代价。同样，在一次收缩前，势也累积到了表中数据项的数量。
除此之外，numi表示表中第i个操作后存储的数据项的数量，sizei表示第i个操作后表的规模，αi表示第i个操作后的装载因子，Φi表示第i个操作后的势。初始时，num0=0，size0=0，α0=1，Φ0=0。
首先分析第i个操作为TABLE-INSERT的情况。若αi-1≥1/2，分析与【4.1 表扩张】一节的分析相同，即：
1、如果第i个TABLE-INSERT操作没有触发扩张，那么有sizei=sizei-1，此操作的平摊代价为：
2、如果第i个TABLE-INSERT操作触发了一次扩张，则有sizei=2·sizei-1及sizei-1=numi-1=numi-1，这意味着sizei=2·(numi-1)。因此，此操作的平摊代价为：
无论表是否扩张，操作的平摊代价：
至多为3。若αi-1<1/2，则第i个操作并不能令表扩张，因为只有当αi-1=1时表才会扩张。若αi也小于1/2，则第i个操作的平摊代价为：
若αi-1<1/2但αi≥1/2，则：
因此，一个TABLE-INSERT操作的平摊代价至多为3。下面分析第i个操作是TABLE-DELETE的情况。在此情况下，numi=numi-1-1。若αi-1<1/2，则必须考虑删除操作是否引起表收缩。如果未引起表收缩操作，则sizei=sizei-1且操作的平摊代价为：
若αi-1<1/2且第i个操作触发了收缩操作，则操作的实际代价为ci=numi+1，因为删除了一个数据项，又移动了numi个数据项。有：sizei/2=sizei-1/4=numi-1=numi+1，因此操作的平摊代价为：
当第i个操作是TABLE-DELETE且αi-1≥1/2时，平摊代价上界是一个常数(书上未给出详细过程)。
在生物应用中，经常需要比较两个(或多个)不同生物体的DNA。一个DNA串由一串称为碱基(base)的分子组成，碱基有腺嘌呤、鸟嘌呤、胞嘧啶和胸腺嘧啶4种类型。用英文单词首字母表示4种碱基，这样就可以将一个DNA串表示为有限集{A,C,G,T}上的一个字符串。例如，某种生物的DNA可能为S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA，另一种生物的DNA可能为S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA。比较两个DNA串的一个原因是希望确定它们的“相似度”，作为度量两种生物相近程度的指标。可以用很多不同的方式来定义相似度，例如：如果一个DNA串是另一个DNA串的子串，那么可以说它们是相似的。但在上面的例子中，S1和S2都不是对方的子串。也可以这样来定义相似性：如果将一个串转换为另一个串所需的操作很少，那么可以说两个串是相似的。另一种衡量串S1和S2的相似度的方式是：寻找第三个串S3，它的所有碱基也都出现在S1和S2中，且在三个串中出现的顺序都相同，但在S1和S2中不要求连续出现。可以找到的S3越长，就可以认为S1和S2的相似度越高。在上述例子中，最长的S3为GTCGTCGGAAGCCGGCCGAA。
一个给定序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。其形式化定义为：给定一个序列X=<x1,x2,…,xm>，另一个序列Z=<z1,z2,…,zk>满足如下条件时称为X的子序列(subsequence)，即存在一个严格递增的X的下标序列<i1,i2,…,ik>，对所有j=1,2,…,k，满足xij=zj。例如，Z=<B,C,D,B>是X=<A,B,C,B,D,A,B>的子序列，对应的下标序列为<2,3,5,7>。
给定两个序列X和Y，如果Z既是X的子序列，也是Y的子序列，称它是X和Y的公共子序列(common subsequence)。例如，如果X=<A,B,C,B,D,A,B>，Y=<B,D,C,A,B,A>，那么序列<B,C,A>就是X和Y的公共子序列。但它不是X和Y的最长公共子序列(LCS)，因为它长度为3，而<B,C,B,A>也是X和Y的公共子序列，其长度为4。<B,C,B,A>是X和Y的最长公共子序列，<B,D,A,B>也是，因为X和Y不存在长度大于等于5的公共子序列。
最长公共子序列问题(longest-common-subsequence problem)给定两个序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，求X和Y长度最长的公共子序列。
下面将展示如何用动态规划方法高效地求解LCS问题。
如果用暴力搜索方法求解LCS问题，就要穷举X的所有子序列，对每个子序列检查它是否也是Y的子序列，然后还需要记录找到的最长子序列。X的每个子序列对应X的下标集合{1,2,…,m}的一个子集，所以X有2m个子序列，因此暴力方法的运行时间为指数阶，对较长的序列是不实用的。
但是，如下面的定理所示，LCS问题具有最优子结构性质，子问题的自然分类对应两个输入序列的“前缀”对。前缀的严谨定义为：给定一个序列X=<x1,x2,…,xm>，对i=0,1,…,m，定义X的第i前缀为Xi=<x1,x2,…,xi>。例如，若X=<A,B,C,B,D,A,B>，则X4=<A,B,C,B>，X0为空串。
定理A：LCS的最优子结构：令X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为两个序列，Z=<z1,z2,…,zk>为X和Y的任意LCS：
1、如果xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS。
2、如果xm≠yn，则zk≠xm意味着Z是Xm-1和Y的一个LCS。
3、如果xm≠yn，则zk≠yn意味着Z是X和Yn-1的一个LCS。
证明：
1、如果zk≠xm，那么可以将xm=yn追加到Z的末尾，得到X和Y的一个长度为k+1的公共子序列，与Z是X和Y的最长公共子序列的假设矛盾。因此，必然有zk=xm=yn，则前缀Zk-1是Xm-1和Yn-1的一个长度为k-1的公共子序列。需要证明Zk-1是一个LCS。利用反证法——假设存在Xm-1和Yn-1的一个长度大于k-1的公共子序列W，则将xm=yn追加到W的末尾会得到X和Y的一个长度大于k的公共子序列，矛盾。
2、如果zk≠xm，那么Z是Xm-1和Y的一个公共子序列。如果存在Xm-1和Y的一个长度大于k的公共子序列W，那么W也是Xm和Y的公共子序列，与Z是X和Y的最长公共子序列的假设矛盾。
3、与情况2对称。
根据上述定理，两个序列的LCS包含两个序列的前缀的LCS。因此，LCS问题具有最优子结构性质。
在【5.1 刻画最长公共子序列的特征】一节的定理A意味着，在求X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的一个LCS时，需要求解一个或两个子问题。如果xm=yn，应该求解Xm-1和Yn-1的一个LCS。将xm=yn追加到这个LCS的末尾，就得到X和Y的一个LCS。如果xm≠yn，则必须求解两个子问题：求Xm-1和Y的一个LCS与X和Yn-1的一个LCS。两个LCS较长者即为X和Y的一个LCS。由于这些情况覆盖了所有可能性，因此知道必然有一个子问题的最优解出现在X和Y的LCS中。
可以很容易看出LCS问题的重叠子问题性质。为了求X和Y的一个LCS，可能需要求X和Yn-1的一个LCS及Xm-1和Y的一个LCS。但是这几个子问题都包含求解Xm-1和Yn-1的LCS的子子问题。很多其他子问题也都共享子子问题。
与矩阵链乘法问题相似，设计LCS问题的递归算法首先要建立最优解的递归式。定义c[i,j]表示Xi和Yj的LCS的长度。如果i=0或j=0，即一个序列长度为0，那么LCS的长度为0。根据LCS问题的最优子结构性质，可得如下递归公式B：
观察到在递归公式B中，通过限制条件限定了需要求解哪些子问题。当xi=yj时，可以而且应该求解子问题：Xi-1和Yj-1的一个LCS。否则，应该求解两个子问题：Xi和Yj-1的一个LCS及Xi-1和Yj的一个LCS。
根据在【5.2 一个递归解】一节的递归公式B，可以很容易地写出一个指数时间的递归算法来计算两个序列的LCS的长度。但是，由于LCS问题只有Θ(m·n)个不同的子问题，可以用动态规划方法自底向上地计算。
下面的LCS-LENGTH伪代码接受两个序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为输入。它将c[i,j]的值保存在表c[0…m,0…n]中，并按行主次序(row-major order)计算表项(即首先由左至右计算c的第一行，然后计算第二行，依此类推)。过程还维护一个表b[1…m,1…n]，帮助构造最优解。b[i,j]指向的表项对应计算c[i,j]时所选择的子问题最优解。过程返回表b和表c，c[m,n]保存了X和Y的LCS的长度。
下图(记为图C)显示了LCS-LENGTH对输入序列X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>计算出的表c和表b。过程的运行时间为Θ(m·n)，因为每个表项的计算时间为Θ(1)。
图C中第i行和第j列的方格包含了c[i,j]的值和b[i,j]记录的箭头。表项c[7,6]中的4即为X和Y的一个LCS<B,C,B,A>的长度。对所有i,j>0，表项c[i,j]仅依赖于是否xi=yj以及c[i-1,j]、c[i,j-1]和c[i-1,j-1]的值，这些值都会在c[i,j]之前计算出来。为了构造LCS中的元素，从右下角开始沿着b[i,j]的箭头前进即可，如图中阴影方格序列。阴影序列中每个“↖”对应的表项(高亮显示)表示xi=yj是LCS的一个元素。
注意第3行是return空格。对于【5.3 计算LCS的长度】一节的图C中的表b，LCS-LENGTH会打印出BCBA。过程的运行时间为O(m+n)，因为每次递归调用i和j至少有一个会减少1。
一旦设计出一个算法，通常情况下都会发现它在时空开销上有改进的余地。一些改进可以简化代码，将性能提高常数倍，但除此之外不会产生性能方面的渐近性提升。而另一些改进可以带来时空上巨大的渐近性提升。
例如，对LCS算法，完全可以去掉表b。每个c[i,j]项只依赖于表c中的其他三项：c[i-1,j]、c[i,j-1]和c[i-1,j-1]。给定c[i,j]的值，可以在O(1)时间内判断出在计算c[i,j]时使用了这三项中的哪一项。因此，可以用一个类似PRINT-LCS的过程在O(m+n)时间内完成重构LCS的工作，而且不必使用表b。但是，虽然这种方法节省了Θ(m·n)的空间，但计算LCS所需的辅助空间并未渐近减少，因为无论如何表c都需要Θ(m·n)的空间。
不过，LCS-LENGTH的空间需求是可以渐近减少的，因为在任何时刻它只需要表c中的两行：当前正在计算的一行和前一行。如果只需计算LCS的长度，这一改进是有效的。但如果需要重构LCS中的元素，这么小的表空间所保存的信息不足以在O(m+n)时间内完成重构工作。
假定需要设计一个程序，实现英语文本到法语的翻译。对英语文本中出现的每个单词，需要查找对应的法语单词。为了实现这些查找操作，可以创建一棵二叉搜索树，将n个英语单词作为关键字，对应的法语单词作为关联数据。由于对文本中的每个单词都要进行搜索，希望花费在搜索上的总时间尽量少。由于单词出现的频率是不同的，像“the”这种频繁使用的单词有可能位于搜索树中远离根的位置上，而像“machicolation”这种很少使用的单词可能位于靠近根的位置上。这样的结构会减慢翻译的速度，因为在二叉树搜索树中搜索一个关键字需要访问的结点数等于包含关键字的结点的深度加1。最好是让文本中频繁出现的单词被置于靠近根的位置。而且，文本中的一些单词可能没有对应的法语单词，这些单词根本不应该出现在二叉搜索树中。在给定单词出现频率的前提下，应该如何组织一棵二叉搜索树，使得所有搜索操作访问的结点总数最少呢？
这个问题称为最优二叉搜索树(optimal binary search tree)问题。其形式化定义为：给定一个由n个不同关键字构成的已排好序的序列K=<k1,k2,…,kn>，其中k1<k2<…<kn，现在使用这些关键字构造一棵二叉搜索树。对每个关键字ki，都有一个概率pi表示其搜索频率。有些要搜索的值可能不在K中，因此还有n+1个“伪关键字”d0,d1,d2,…,dn表示不在K中的值。d0表示所有小于k1的值，dn表示所有大于kn的值，对i=1,2,…,n-1，伪关键字di表示所有在ki和ki+1之间的值。对每个伪关键字di，也都有一个概率qi表示对应的搜索频率。下下一张图显示了根据一个n=5的关键字集合及如下的搜索概率：
构造的两棵二叉搜索树：
上图(记为图D)中：
1、a：期望搜索代价为2.80的二叉搜索树。
2、b：期望搜索代价为2.75(最优)的二叉搜索树。
每个关键字ki是一个内部结点，而每个伪关键字di是一个叶结点。每次搜索要么成功(找到某个关键字ki)要么失败(找到某个伪关键字di)，因此有如下公式(记为公式E)：
由于知道每个关键字和伪关键字的搜索概率，因而可以确定在一棵给定的二叉搜索树T中进行一次搜索的期望代价。假定一次搜索的代价等于访问的结点数，即此次搜索找到的结点在T中的深度再加1。那么在T中进行一次搜索的期望代价为：
其中depthT表示一个结点在树T中的深度。最后一个等式是由公式E推导而来。在图D的(a)中，逐结点计算期望搜索代价：
对于一个给定的概率集合，希望构造一棵期望搜索代价最小的二叉搜索树，称之为最优二叉搜索树。在图D的(b)所示的二叉搜索树就是给定概率集合的最优二叉搜索树，其期望代价为2.75。这个例子显示，最优二叉搜索树不一定是高度最矮的。而且，概率最高的关键字也不一定出现在二叉搜索树的根结点。在此例中，关键字k5的搜索概率最高，但最优二叉搜索树的根结点为k2。
与矩阵链乘法问题相似，对本问题来说，穷举并检查所有可能的二叉搜索树不是一个高效的算法。对任意一棵n个结点的二叉树，都可以通过对结点标记关键字k1,k2,…,kn构造出一棵二叉搜索树，然后向其中添加伪关键字作为叶结点。
下面将使用动态规划方法求解此问题。
为了刻画最优二叉搜索树的结构，先来观察子树的特征。考虑一棵二叉搜索树的任意子树。它必须包含连续关键字ki,…,kj，1≤i≤j≤n，而且其叶结点必然是伪关键字di-1,…,dj。
二叉搜索树问题的最优子结构为：如果一棵最优二叉搜索树T有一棵包含关键字ki,…,kj的子树T’，那么T’必然是包含关键字ki,…,kj和伪关键字di-1,…,dj的子问题的最优解。下面用“剪切-粘贴”法来证明这一结论。如果存在子树T"，其期望搜索代价比T’低，那么将T’从T中删除，将T"粘贴到相应位置，从而得到一棵期望搜索代价低于T的二叉搜索树，与T最优的假设矛盾。
现在需要利用最优子结构性质来证明——可以用子问题的最优解构造原问题的最优解。给定关键字序列ki,…,kj，其中某个关键字，比如说kr(i≤r≤j)是这些关键字的最优子树的根结点。那么kr的左子树就包含关键字ki,…,kr-1(和伪关键字di-1,…,dr-1)，而右子树包含关键字kr+1,…,kj(和伪关键字dr,…,dj)。只要检查所有可能的根结点kr(i≤r≤j)，并对每种情况分别求解包含ki,…,kr-1及包含kr+1,…,kj的最优二叉搜索树，即可保证找到原问题的最优解。
注意“空子树”。假定对于包含关键字ki,…,kj的子问题，选定ki为根结点。根据前面的讨论，ki的左子树包含关键字ki,…,ki-1。将此序列解释为不包含任何关键字。但子树仍然包含伪关键字。包含关键字序列ki,…,ki-1的子树不含任何实际关键字，但包含单一伪关键字di-1。对称地，如果选择kj为根结点，那么kj的右子树包含关键字kj+1,…,kj——此右子树不包含任何实际关键字，但包含伪关键字dj。
现在选取子问题域为：求解包含关键字ki,…,kj的最优二叉搜索树，其中i≥1，j≤n且j≥i-1(当j=i-1时，子树不包含实际关键字，只包含伪关键字di-1)。定义e[i,j]为在包含关键字ki,…,kj的最优二叉搜索树中进行一次搜索的期望代价。最终希望计算出的是e[1,n]。
j=i-1的情况最为简单，由于子树只包含伪关键字di-1，因此期望搜索代价为e[i,i-1]=qi-1。
当j≥i时，需要从ki,…,kj中选择一个根结点kr，然后构造一棵包含关键字ki,…,kr-1的最优二叉搜索树作为其左子树，以及一棵包含关键字kr+1,…,kj的二叉搜索树作为其右子树。当一棵子树成为一个结点的子树时，由于每个结点的深度都增加了1，根据公式：
这棵子树的期望搜索代价的增加值应为所有概率之和。对于包含关键字ki,…,kj的子树，所有概率之和为：
因此，若kr为包含关键字ki,…,kj的最优二叉搜索树的根结点，有如下公式：
注意：
因此e[i,j]可重写为：
上图的公式假定现在知道了哪个结点kr应该作为根结点。如果选取期望搜索代价最低者作为根结点，可得最终递归公式：
e[i,j]的值给出了最优二叉搜索树的期望搜索代价。为了记录最优二叉搜索树的结构，对于包含关键字ki,…,kj(1≤i≤j≤n)的最优二叉搜索树，定义root[i,j]保存根结点kr的下标r。
求解最优二叉搜索树和矩阵链乘法拥有一些相似之处。它们的子问题都由连续的下标子域组成。需要设计一个高效算法，用一个表e[1…n+1,0…n]来保存e[i,j]值。第一维下标上界为n+1而不是n，原因在于对于只包含伪关键字dn的子树，需要计算并保存e[n+1,n]。第二维下标下界为0，是因为对于只包含伪关键字d0的子树，需要计算并保存e[1,0]。只使用表中满足j≥i-1的表项e[i,j]，除此之外还使用一个表root，表项root[i,j]记录包含关键字ki,…,kj的子树的根，只使用此表中满足1≤i≤j≤n的表项root[i,j]。
还需要另一个表来提高计算效率。为了避免每次计算e[i,j]时都重新计算w(i,j)，将这些值保存在表w[1…n+1,0…n]中，这样每次可节省Θ(j-i)次加法。对基本情况，令w[i,i-1]=qi-1(1≤i≤n+1)。对j≥i的情况，可如下计算：
下面的伪代码接受概率列表p1,…,pn和q0,…,qn及规模n作为输入，返回表e和root：
在上述代码中：
1、第3-5行的for循环初始化e[i,i-1]和w[i,i-1]的值。
2、第6-15行的for循环对所有1≤i≤j≤n计算e[i,j]和w[i,j]。在第一个循环步中，l=1，循环对所有i=1,2,…,n计算e[i,i]和w[i,i]。第二个循环步中，l=2，对所有i=1,2,…,n-1计算e[i,i+1]和w[i,i+1]，依此类推。
3、第11-15行的内层for循环，逐个尝试下标r，确定哪个关键字kr作为根结点可以得到包含关键字ki,…,kj的最优二叉搜索树。这个for循环在找到更好的关键字作为根结点时，会将其下标r保存在root[i,j]中。
下下一张图给出了OPTIMAL-BST输入下图中的关键字分布：
后计算出的表e[i,j]、w[i,j]和root[i,j]：
上图中的表进行了旋转——对角线旋转到了水平方向。OPTIMAL-BST按自底向上的顺序逐行计算，在每行中由左至右计算每个表项。
END
一、问题一个二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。示例 1：输入：root = [1,3,null,null,2]输出：[3,1,null,null,2]解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。示例 2：输入：roo
二叉查找树（Binary Search Tree，简称BST）是一种常用的数据结构，它能够高效地进行查找、插入和删除操作。二叉查找树的特点是，对于树中的每个节点，其左子树中的所有节点都小于该节点，而右子树中的所有节点都大于该节点。
完全二叉树我们知道树是一种非线性数据结构。它对儿童数量没有限制。二叉树有一个限制，因为树的任何节点最多有两个子节点：左子节点和右子节点。什么是完全二叉树？完全二叉树是一种特殊类型的二叉树，其中树的所有级别都被完全填充，除了最低级别的节点从尽可能左侧填充之外。
给定一个由n个互异的关键字组成的有序序列K={k123n}和它们被查询的概率P={p1,p2,p3,……,pn}，要求构造一棵二叉查找树T，使得查询所有元素的总的代价最小。对于一个搜索树，当搜索的元素在树内时，表示搜索成功。当不在树内时，表示搜索失败，用一个“虚叶子节点”来标示搜索失败的情况，因此需要n+1个虚叶子节点{d01n}，对于应di的概率序列是Q={q0,q1,……,qn}。其中d0表示
最长公共子序列(Longest Common Subsequence，LCS)即求两个序列最长的公共子序列(可以不连续)。比如3 2 1 4 5和1 2 3 4 5两个序列，最长
问题描述：给定两个序列，例如 X = “ABCBDAB”、Y = “BDCABA”，求它们的最长公共子序列的长度。下面是求解时的动态
一个字符串S，去掉零个或者多个元素所剩下的子串称为S的子序列。最长公共子序列就是寻找两个给定序列的子序列，该子序列在两个序列中以相同的顺序出现，但是不必要是连续的。例如序列X=ABCBDAB，Y=BDCABA。序列BCA是X和Y的一个公共子序列，但是不是X和Y的最长公共子序列，子序列BCBA是X和Y的一个LCS，序列BDAB也是。寻找LCS的一种方法是枚举X所有的子序列，然后注意检查是否是Y的子序
先上二叉树查找树的删除的代码，因为删除是二叉查找树最复杂的操作：int BinarySearchTree::tree_re
1、问题描速： 设 S={x1, x2, ···, xn} 是一个有序集合，且x1, x2, ···, xn表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素，而且具有性质：存储于每个顶点中的
问题 A: 最长公共子序列时间限制:1 Sec内存限制:32 MB提交:520解决:288[提交][状态][讨论版][命题人:外部导入]题目描述给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。例如：Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列，...
最长公共子序列（Longest Common Subsequence, LCS）问题是计算给定两个序列的最长子序列的长度，这个子序列不要求连续
# 最长公共子序列算法## 简介最长公共子序列算法（Longest Common Subsequence，简称LCS算法）是一种常用的动态规划算法，用于解决字符串序列的最长公共子序列问题。最长公共子序列是指两个字符串序列中，最长的且在两个序列中按原顺序连续出现的子序列。LCS算法常用于字符串比对、版本控制、DNA比对等领域。在字符串比对中，LCS算法可以用于比较两个文本文件的差异，从而
最长公共子序列不要求连续，最长公共子串要求连续。在最长公共子序列中，可以另外用数组记录其过程，用回溯法求出最长子序列。
最长公共子
最长公共子序列：一个序列 S 。假设各自是两个或多个已知序列的子序列，且是全部符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。 其核心非常easy： 这样，构造子结构就比較简单了： if(str1[i - 1] == str2[j - 1]) m[i][j] = m[i - 1][j
定义 dp[ i ][ j ]表示s1...si与t1...tj对应的LCS长度 转移（缩小问题规模） 当s[ i+1] = t [ j+1]时，dp[ i + 1 ][ j + 1 ] = dp[ i ][ j ] + 1时。 因为这个元素构成了LCS的一部分，删除它就是删除了LCS的一部分。 对 ...
最长公共子序列（LCS）最常见的算法是时间复杂度为O(n^2)的动态规划(DP)算法，但在James W. Hunt和Thomas G. Szymansky 的论文"A Fast Algorithm for Computing Longest Common Subsequence"中，给出了O(nlogn)下限的一种算法。 定理：设序列A长度为n，{A(i)}，序列B长度为m，{B(i)
张量相乘核心结论：需先明确乘法类型（元素积/矩阵积/点积），不同类型对应不同维度要求，结果维度由乘法规则决定，核心分三类常见运算。 一、元素积（Hadamard积）：对应元素直接相乘 核心要求：张量维度必须完全一致（无需广播，广播仅适用于加减，不适用于元素积）。 运算逻辑：两个张量相同位置的元素逐一 ...
彻底移除CentOS 7系统中的MongoDB数据库，需要进行以下步骤： 停止MongoDB服务：首先确保MongoDB服务已经停止，可以通过下面的命令来执行这一操作： sudo systemctl stop mongod 如果您的MongoDB服务名称不是默认的 mongod，请将上述命令中的 m ...
知识管理系统：软件工业化转型的神经中枢 在数字化转型浪潮中，软件开发正经历着从"手工作坊"到"工业化生产"的深刻变革。这一变革的核心驱动力，正是知识管理系统的全面升级与重构。如同制造业从手工装配到智能流水线的演进，软件产业也正在通过知识管理的标准化、模块化和智能化，实现研发效能的质变飞跃。 制造业4 ...
S2SH后台商用权限系统第一讲各位博友： 您好！从今天开始我们做一套商用的权限系统。功能包含用户管理、角色管理、模块管理、权限管理。大家知道每个商用系统肯定会拥有一套后台系统，我们所讲的权限系统是整个系统核心部分。本套系统技术有struts2、Spring IOC 、hibernate、mysql、jquery，也就是目前公司最流行的S2SH框架技术
主旨：从应用角度理解是通过定时器功能实现。MCPWM需高级配置高级定时器实现输出。 一，定时器原理 1.1 LKS 基本定时器和ST 基本定时器 LKS 有4个括 4 个独立的Timer（时基），都有2个通道，可以独立配置运行计数,0/1为16bit(65535) 2/3为32bit。每个Timer ...