数据结构和算法学习笔记(经典)

《数据结构和算法学习笔记(经典)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、希赛，中国最大的IT资源平台一、复杂性分析常用的大Ο大Θ大Ω就不说了，一般知道大Ο也就行了。这里主要说说补偿分析法（amortizedanalysis），有的翻译成均（平）摊分析。英文单词amortized的意思是分期付款，这个比较容易理解。在数据结构中的应用例子有移至前端的自组织线性表，自适应树等。在一些应用中，数据结构是从属于一系列操作而不是一个操作的，这时，我们分析最坏的情况时就不能分析每一个操作的最坏情况，然后认为整个操作序列的最坏情况就是单个最坏情况的和。最简单的例子是二进制计数器。假设一个从0开始的n位计数器。用数组A

2、[0…n-1]来表示，A[0]存最低位。对它加1的算法如下：Increment(A){for(i=0;i

3、属于原作者希赛，中国最大的IT资源平台否有关系，如果这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，

4、那么下次只有1次变化。因此我们可以把这一序列操作看成一个整体，求出所有的操作的复杂度然后除以m。为了简便，我们假设从0开始计数，共计数m＝n2次，（从00…00到11..11）。我们来分析第0位，000000，000001,000010,000011,…….发现每2（隔一）个数变化一次，类似的第1位每4个数变化一次，……i所以第i位变化m/2次，0<=i<=n-1n−1ni1i=2m所有的变化次数为：∑m/2

5、作的总代价的上界T(m)，每个操作的平均为T(m)/m。注：本文来源互联网，由希赛网下载频道整理发布，版权属于原作者希赛，中国最大的IT资源平台这种方法的适用场合是：这m个操作的总代价比较容易求。但有时候我们根本不知道具体的操作到底是什么。比如移至前端的自组织线性表。我们根本不知道m次操作会访问哪些数据。这个问题是：为了提高链表的查询速度，“用最近的过去预测最近的将来”，把最近访问过的元素提到表头，这样如果下次再访问这个数据，就很快可以找到。你可能和我一样担心会不会“万一放到表头的元素都不再或很少再次被访问”，那把它提到表头不但徒

6、劳无功，而且使下一个被访问的元素（如果它在原链表中的位置在被提到表头的元素之前）后退了一个位置？假设一共进行了m次查询，但不知道每次到底查询哪个数据。那怎么计算复杂性呢？比如，m次都访问某一个元素ai，则一共需要（i+m-1），若m>n，则（i+m-1）/m<(n+m-1)/m<2。比较糟糕的情况是访问顺序是anan-1……a1。则每次访问都要比较n次。可见m次操作的复杂性与每次操作有关。那我们怎么评价把最近访问过的数据移到表头是好是坏呢？我们可能希望把它和“最好的”链表比较。“最好的”链表是什么样子的呢？当然如果每次访问的数据都

7、在表头那就太好了，但我们没法知道下一次访问哪个元素，否则把它移到表头就可以了。有n个元素的链表，有n！种不同的排列。对每一种访问序列，都至少有一个是最好的。比如访问序列是a1a1…….a1a1，最好的链表之一是a1a2…….an。我们发现如果链表不是动态的，则最好的链表应该是把访问次数最多的放在前面，访问次数少的放后面。证明也很容易，使用不等式逆注：本文来源互联网，由希赛网下载频道整理发布，版权属于原作者希赛，中国最大的IT资源平台序和<乱序和<顺序和即可。如果我们知道每个元素的访问次数的话，就可以构造这样一个链表，可惜元素的访问

8、次数我们也是不知道的。也就是说不同的访问序列有不同的“最好的”链表。我们能不能得到一个链表，不论访问序列是什么，我这个链表的访问效率都不比这个访问序列的“最好的”链表相差太多呢（什么叫相差不太多？他们的大O相同？）？显然这个链表必须是动态的，否则我