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

《算法合集之《数据结构的提炼与压缩》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOI2008冬令营论文数据结构的提炼与压缩摘要时间复杂度和空间复杂度是衡量一个数据结构的重要指标，往往，简单存储结构和小存储规模的数据结构会带来较低的时空复杂度。因此，在程序设计中就需要仔细分析问题，化简存储结构，减少存储规模。关键字化简存储结构、减少存储规模、“提炼”、“压”、“缩”、DFS序、BFS序共48页--第48页NOI2008冬令营论文数据结构的提炼与压缩引言作为程序设计的一部分，数据结构在现在的信息学竞赛中起着越来越大的作用。一方面，一个好的数据结构是高效实现算法的基础，例如当算法设计动态序关系时，通过平衡排

2、序二叉树维护序关系就要比普通线性结构高效的多；另一方面，的信息学竞赛中已经涌现出一大批“赤裸裸”的数据结构题，即题目所需要的，就是设计一个能维护特定数据关系，能高效完成特定操作的数据结构，例如NOI2007necklace、CEOI2007necklace都是这样的问题。衡量一个程序的优劣，有四个主要的参考度量：时间复杂度，空间复杂度，求解精确度，编程复杂度。时间复杂度衡量程序运行的时间，往往用一个相对输入规模的阶表示，例如冒泡排序的时间复杂度是O(n2)；空间复杂度用来衡量程序所需的除读入外的额外内存空间，往往也用一个相对

3、输入规模的阶表示，例如KMP算法的空间复杂度是O(n)；求解精确度衡量程序输出解的质量，往往用与最优解之间的相对或绝对误差来描述，现在的信息学竞赛中大多数问题不允许有误差，而另一些问题将求解精确度作为评分尺度之一；编程复杂度衡量正确编程和程序调试的困难程度。而作为对数据结构优劣的评判，（在编程复杂度不过分高的前提下）一个数据结构的时空复杂度就显得最为重要。本文将主要讨论的通过“化繁为简”的手段优化数据结构的时空复杂度。“化繁为简”作为一个可以广泛应用的方法，它能给程序设计带来以下两方面的优势。一方面，直观地看，在规模小、结构

4、简单的数据上进行操作，时空耗费比起规模大、结构复杂的数据在操作规模上“天生”就有着无与伦比的优势。例如，图结构的存储无论是采取邻接矩阵还是邻接表，空间都是O(m+n)，只要不是稀疏图，就会占用平方阶的空间，同时，所有基本操作的时间复杂度也在平方阶之上；但对于树结构而言，常用的左儿子右兄弟表示法只需要O(n)的空间复杂度，像遍历这样的基本操作，时间复杂度也是O(n)。共48页--第48页NOI2008冬令营论文数据结构的提炼与压缩另一方面，一个简单的数据结构可以有更多的处理手段，也适应于更多的算法。例如，在图结构上，一般只能进

5、行连通性判断，流算法（事实上，流算法实现中利用到了树结构）等；而在树结构上，就可以实施树型动态规划；更进一步，对于线性结构而言，DP（DynamicProgramming，动态规划）的形式更加灵活，而且还可以使用线段树，树状数组等工具；另外，如果线性结构辅助序关系，那么各种平衡BST(BinarySearchTree，二叉搜索树)也能有用武之地。本文将提出三种常见的化繁为简的手段(i)提炼：忽略无效信息，减少存储规模(ii)压：调整存储方式，化简存储结构(iii)缩：合并重复信息，减少存储规模共48页--第48页NOI200

6、8冬令营论文数据结构的提炼与压缩1．二维结构的化简二维结构主要分两种情况，其一：两维对称，即矩阵的情况；其二：两维不对称，即一个线性表，它的每个元素都是一维结构，串数组是常见的情况。下面我们分别就这两种情况举个例子。问题一：ural1568Traincarsorting问题描述：对于一个序列，定义一种操作，将a变成b，使得：，…，，…。其中s+t=n，，，{，…，，…}={1，2，3…n}。例如：12345可转化为13524。给出一个序列（满足是1到n的一个排列），求一种方案，通过最少的操作次数是它变成升序序列。这一题从题面

7、看，操作的定义比较复杂，没有一个明显的切入点，很难设计出一个能有效解决它的算法。其实只要找到题目中涉及的操作对应的不变量，问题就能迎刃而解。为算法刻画和证明的方便，引入以下定义：称一个的矩阵A为序列的母矩阵，当且仅当，矩阵A中的所有非零元素，自上到下自左到右逐列读出得到，自左到右自下到上逐行读出得到升序序列。称序列的所有母矩阵中，行数列数都最小的那个矩阵为序列的最简母矩阵。例如：当n=5时，{5，3，2，4，1}的最简母矩阵为。本题的算法只需要完成以下步骤即可。(i)判断当前是否是升序序列，若是则打印输出结束程序，若否转(i

8、i)(ii)计算的最简母矩阵A（设A是一个的矩阵）共48页--第48页NOI2008冬令营论文数据结构的提炼与压缩(i)对进行如下题意中的操作：A的偶数行全部非零元素自左到右自上到下逐行读出得到，A的奇数行全部非零元素自左到右自上到下逐行读出得到。重复(i)。算法证明如下：只需证明：算法中