算法合集之《数据结构的提炼与压缩》.doc

NOI2008冬令营论文 数据结构的提炼与压缩摘要时间复杂度和空间复杂度是衡量一个数据结构的重要指标，往往，简单存储结构和小存储规模的数据结构会带来较低的时空复杂度因此，在程序设计中就需要仔细分析问题，化简 存储结构，减少存储规模关键字化简存储结构、减少存储规模、“提炼”、“压”、“缩”、DFS序、BFS序引言作为程序设计的一部分，数据结构在现在的信息学竞赛中起着越来越大的作用一方面，一个好的数据结构是高效实现算法的基础，例如当算法设计动态序关系时，通过平衡排序二叉树维护序关系就要比普通线性结构高效的多；另一方面，的信息学竞赛中已经涌现出一大批“赤裸裸”的数据结构题，即题目所需要的，就是设计一个能维护特定数据关系，能高效完成特定操作的数据结构，例如NOI2007 necklace、CEOI2007 necklace都是这样的问题衡量一个程序的优劣，有四个主要的参考度量：时间复杂度，空间复杂度，求解精确度，编程复杂度时间复杂度衡量程序运行的时间，往往用一个相对输入规模的阶表示，例如冒泡排序的时间复杂度是O(n2)；空间复杂度用来衡量程序所需的除读入外的额外内存空间，往往也用一个相对输入规模的阶表示，例如KMP算法的空间复杂度是O(n)；求解精确度衡量程序输出解的质量，往往用与最优解之间的相对或绝对误差来描述，现在的信息学竞赛中大多数问题不允许有误差，而另一些问题将求解精确度作为评分尺度之一；编程复杂度衡量正确编程和程序调试的困难程度。

而作为对数据结构优劣的评判，（在编程复杂度不过分高的前提下）一个数据结构的时空复杂度就显得最为重要本文将主要讨论的通过“化繁为简”的手段优化数据结构的时空复杂度化繁为简”作为一个可以广泛应用的方法，它能给程序设计带来以下两方面的优势一方面，直观地看，在规模小、结构简单的数据上进行操作，时空耗费比起规模大、结构复杂的数据在操作规模上“天生”就有着无与伦比的优势例如，图结构的存储无论是采取邻接矩阵还是邻接表，空间都是O(m+n)，只要不是稀疏图，就会占用平方阶的空间，同时，所有基本操作的时间复杂度也在平方阶之上；但对于树结构而言，常用的左儿子右兄弟表示法只需要O(n)的空间复杂度，像遍历这样的基本操作，时间复杂度也是O(n) 另一方面，一个简单的数据结构可以有更多的处理手段，也适应于更多的算法例如，在图结构上，一般只能进行连通性判断，流算法（事实上，流算法实现中利用到了树结构）等；而在树结构上，就可以实施树型动态规划；更进一步，对于线性结构而言，DP（Dynamic Programming，动态规划）的形式更加灵活，而且还可以使用线段树，树状数组等工具；另外，如果线性结构辅助序关系，那么各种平衡BST (Binary Search Tree，二叉搜索树)也能有用武之地。

本文将提出三种常见的化繁为简的手段(i) 提炼：忽略无效信息，减少存储规模(ii) 压：调整存储方式，化简存储结构(iii) 缩：合并重复信息，减少存储规模1．二维结构的化简二维结构主要分两种情况，其一：两维对称，即矩阵的情况；其二：两维不对称，即一个线性表，它的每个元素都是一维结构，串数组是常见的情况下面我们分别就这两种情况举个例子问题一：ural 1568 Train car sorting问题描述：对于一个序列，定义一种操作，将a变成b，使得：，…，，…其中s+t=n，，，{，…，，…}={1，2，3…n}例如：1 2 3 4 5可转化为1 3 5 2 4给出一个序列（满足是1到n的一个排列），求一种方案，通过最少的操作次数是它变成升序序列这一题从题面看，操作的定义比较复杂，没有一个明显的切入点，很难设计出一个能有效解决它的算法其实只要找到题目中涉及的操作对应的不变量，问题就能迎刃而解为算法刻画和证明的方便，引入以下定义：称一个的矩阵A为序列的母矩阵，当且仅当，矩阵A中的所有非零元素，自上到下自左到右逐列读出得到，自左到右自下到上逐行读出得到升序序列称序列的所有母矩阵中，行数列数都最小的那个矩阵为序列的最简母矩阵。

例如：当n=5时，{5，3，2，4，1}的最简母矩阵为本题的算法只需要完成以下步骤即可i) 判断当前是否是升序序列，若是则打印输出结束程序，若否转(ii)(ii) 计算的最简母矩阵A（设A是一个的矩阵）(iii) 对进行如下题意中的操作：A的偶数行全部非零元素自左到右自上到下逐行读出得到，A的奇数行全部非零元素自左到右自上到下逐行读出得到重复(i)算法证明如下：只需证明：算法中给出的解是最优的，即操作步骤最少的首先：的最简母矩阵A，经上面的(iii)后，将成为一个行的矩阵这是因为，…，其中表示A的第k行中非零元素构成的集合，对应A经操作后得到的矩阵B）其次：是一个升序序列，当且仅当，他的最简母矩阵是一个的矩阵例如：a=，b=，可得到最简母矩阵A=，则得到B=；由上面这两个事实可以得到，算法中给出的方案含有且只含有个步骤下面证明，这是最优的这只需证明：若的最简母矩阵有p行，则一次操作后得到的最简母矩阵至少有行我们用反证法假设存在一种操作方案，使得的最简母矩阵B只有行，则由抽屉原则，必定存在B的一行(不妨设为第行)，使得其中含有来自A的不同的三行的非零元素（因为2<），设其中分别来自第行不妨<<，则由性质二（在A中）知：>>。

这样又由性质二（在B中），在B中第行中从左到右依次是所以，由性质一（在B中），在中出现的先后顺序为先，再，最后再由抽屉原则，中必有两个，同属于以下两个集合之一：{，…}，{，…}不妨设同属于{，…}这样，、在中出现的先后顺序与中相同即在中也是先出现后出现我们考虑以下这些数：，+1，+2…-1，一方面，由于、在B中同行，由性质二（在B中），所有这些数在B中也同行，且位置介于、之间所以，他们在中按照顺序依次（不一定连续）出现同时，由性质一，他们一定同属于{，…}，所以，他们在中也按照顺序依次（不一定连续）出现另一方面，由性质二（在A中），他们在A中的行号介于[,]，且严格不增由于在A中不同行，所以其中必有相邻两个数在A中不同行，设为、+1由性质二，、+1一定处在相邻两行否则，他们中间的行只能全零，那这些行就可以省略，这与A的最简性是矛盾的另外，由前面的结论，在中先出现， +1后出现所以，在A中的列号小于+1的列号即、+1的位置关系是这样的：显然这两行是可以合并的，这与A的最简性矛盾！证毕当然，给出这样一个算法，不是本文的关键注意到这个算法的操作对象是矩阵，如果使用一般的实现方法，不可避免在最坏情况下单次操作的复杂度达到O(n2)，显然，复杂度过高，还有优化余地。

要进一步优化程序，可以着眼数据结构不难发现，矩阵中的非零元素只有n个，因此可以只记录这些元素的位置，这样就等于把矩阵的规模缩小到了O(n)，这一优化方法使得时空复杂度都得到了巨大的改进因此，算法的总时间复杂度是O(n·ans)，同时是输出的复杂度，空间复杂度O(n)，相比朴素实现矩阵的效果时空复杂度都得到了大大改进另外，仔细分析证明，可以发现列数的最优性是可以忽略的这样，在具体实现时让矩阵的每列只有一个元素，使得每个元素的位置信息可以更加简单，程序编码更加简便回顾这一问题的解决，关键在于“提炼”方法的使用忽略了矩阵中的非零元素这一无用信息，从而可以用线性表存储矩阵结构，使时间复杂度从O(n2·ans)降到O(n·ans)，空间复杂度从O(n2) 降到O(n)问题二：CEOI 2007 Day 2 Necklaces问题描述：要求编译一个库，能够对若干已知的整数串进行两个操作：(i) 在某个已知串的左端或右端增加或减少一个元素，得到一个新的已知的串ii) 输出某个已知串的最左端或最右端的数在问题的一开始，只有一个已知的串：空串这道题是一道典型的“赤裸裸”的数据结构题，若要进行n个操作，则最坏情况下，需要维护O(n)个长为O(n)的字符串。

显然，朴素的实现无论在时间上还是空间上总的复杂度都要达到平方阶，这是不能令人满意的分析这道题的特点，发现由于每个串都要由之前的某个串经过微小加工得到，所以，这些串之间一定有很多公共部分不妨利用这一点来优化数据结构首先利用两种特殊情况来帮助思维（见表1）：(i) 在某一串左侧，分别加上不同的元素，得到不同的串这一特例容易让我们想到星形存储ii) 在某一串左侧，加上一列元素，在从右段依次删除这一特例容易让我们想到链形存储加上首尾指针表1 两种特殊情况和它们的存储方式 特殊情况BAACACADACBCCAABCCAABCA 存储方式ABCDABC这样，我们就需要设计一种数据结构，上面的星形和链形统一起来很明显，树形结构可以胜任有了树形的构想，整个数据结构的设计就不难了根据上面的分析，可以维护一个数据结构，称它left-right treeleft tree和right tree都是Trie(字母树)对于每个已知的串s，我们把它任意（实际上不是任意的）分成左右两部分，左串存储在left tree中，右串存储在right tree中这样，我们只需要四个量：left_root, left_leave, right_root, right_leave，就可以描述s：s就由left tree中left_leave到left_root的路径代表的串，与right tree中right_root到right_leave的路径代表的串组成。

下面给出一个left-right tree的例子（见图1）123456789left treeright treeleft_leave left_root right_root right_leave图1 整数串(5，2，1，7，8)在一棵left-right tree中的表示同时，我们允许，左串和右串中任意一串为空，甚至都为空，这时实际s就为空并规定：若在左树中的串为空，则left_root=0；同样若在右树中的串为空，则right_root=0有了这样的数据结构，各个操作的实现已经不难了，只要实现好下面几个情况即可：(i) 已知树中某链的两端点，求底部端点的父亲(ii) 已知树中某链的两端点，求顶部端点在链中的儿子这些看起来都是Trie的基本操作，但由于本题中Trie的元素的规模不受限制，故(ii)的实现并不平凡，因此仍需要探讨，关于树形结构的化简将在第二部分着重讨论总结本题，关键在于，用“缩”的方法，利用Trie，将串数组中的重复数据压缩，用树形结构简化储存，空间复杂度从O(n2)到O(n)，有了质的飞跃对于时间复杂度，要看(i)(ii)的实现，但也是离不开这个树形结构的前提的。

2．树形结构的化简树结构是一种被许多人深入研究过的数据结构，树结构也被用作为各种高级数据结构的基本模型，例如并查集、堆等等本文主要讨论的是图论树同样以两个问题为例：问题三：浙江2007年省选 捉迷藏问题描述：给定一棵树，每个节点要么是黑色，要么是白色，能执行两个操作：把某一个点取反色，返回距离最远的黑色点对这也是一道“赤裸裸”的数据结构题应该说这是众多数据结构题中的一道难题。