数据结构的选择与算法效率

IOI’99中国集训队优秀论文选-21-数据结构的选择与算法效率——从IOI98试题PICTURE谈起【关键字】数据结构的选择线性结构树形结构【摘要】算法+数据结构=程序。设计算法与选择合适的数据结构是程序设计中相辅相成的两方面，缺一不可。数据结构的选择一直是程序设计中的重点、难点，正确地应用数据结构，往往能带来意想不到的效果。反之，如果忽视了数据结构的重要性，对某些问题有时就得不到满意的解答。通过对IOI98试题Picture的深入讨论，我们可以看到两种不同的数据结构在解题中的应用，以及由此得到的不同的算法效率。本文以Picture问题为例，探讨数据结构的选择对算法效率的影响。【正文】引言算法通常是决定程序效率的关键，但一切算法最终都要在相应的数据结构上实现，许多算法的精髓就是在于选择了合适的数据结构作为基础。在程序设计中，不但要注重算法设计，也要正确地选择数据结构，这样往往能够事半功倍。在算法时间与空间效率的两方面，着重分析时间效率，即算法的时间复杂度，因为我们总是希望程序在较短的时间内给出我们所希望的输出。如果在空间上过于“吝啬”而使得时间上无法承受，对解题并无益处。本文对IOI98的试题Picture作一些分析，通过两种不同数据结构的选择，将了解到数据结构对算法本身及算法效率的影响。Picture问题及算法设计一、Picture问题Picture问题是IOI98的一道试题，描述如下：墙上贴着一些海报、照片等矩形，所有的边都为垂直或水平。每个矩形可以被其它矩形部分或完全遮盖，所有矩形合并成区域的边界周长称为轮廓周长。例如图1的三个矩形轮廓周长为30：数据结构的选择与算法效率——从IOI98试题PICTURE谈起-22-IOI’99中国集训队优秀论文选图1要求编写程序计算轮廓周长。数据量限制：0≤矩形数目5000；坐标数值为整数，范围是[-10000，10000]。二、算法描述在算法的大体描述中，将不涉及到具体的数据结构，便于数据结构的进一步选择和比较分析。（一）、轮廓的定义在描述算法前，我们先明确一下“轮廓”的定义：1、轮廓由有限条线段组成，线段是矩形边或者矩形边的一部分。2、组成矩形边的线段不应被任何矩形遮盖。图2与图3分别是遮盖的两种情况。图2图3图4（AB被遮盖）（CD被遮盖）（二）、元线段本题的一大特征是分析矩形的边，而边的端点（即矩形的顶点）坐标为整数，且坐标取值范围已经限定在[-10000，10000]之间。这样，就可以把这个平面理解成为一个网格。由于给出的坐标是整数，所以矩形边一定在网格线上。在网格中，对于一条线段我们最关心其绝对坐标。如图4，我们认为矩形边AB由线段L1、L2、L3组成。像L1、L2、L3这样连接相邻网格顶点的基本线段，称之为“元线段”，这样就把矩形边离散化了。显然，有限的元线段覆盖了所有的网格线，且元线段是组成矩形边乃至组成轮廓的基本单位。一条元线段要么完全属于轮廓，要么完全不属于轮廓。这种定义使我们对问题的研究具体到每一条元线段，这样的离散化处理有利于问题的进一步讨论。（三）、超元线段ABL1L3L2BADCIOI’99中国集训队优秀论文选-23-元线段的引入，使问题更加具体。但也应当看到，平面中共有20001*20000*2条元线段，研究的对象过多，而且计算量受到网格大小的影响，如果顶点坐标范围是[-1,000,000，1,000,000]，元线段数目将达到8*10^12，这是天文数字。因此有必要对“元线段”进行优化。受到元线段的启发，我们定义一种改进后的元线段——“超元线段”，它将由对平面的“切割”得到。具体做法是，根据每个矩形纵向边的横坐标纵向地对平面进行2*N次切割、根据矩形横向边的纵坐标横向地对矩形进行2*N次切割（N为矩形个数）。显然，经过切割后的平面被分成了(2*N+1)^2个区域，如图5所示：图5图6其中像横向边AB、纵向边CD这样的线段就是“超元线段”。超元线段与元线段有着相似的性质，也是组成轮廓的基本单位。所不同的是，超元线段的数目较少，一般为4*N条左右，且超元线段数目不受网格大小的影响。基于超元线段的优点，算法最终将研究超元线段。(一)、离散化及算法框架算法的研究对象是超元线段，但这并不等于逐一枚举，那样耗时过大，而整体考虑又使得问题无从下手。有一种考虑方法是折中的，即既不研究每一条超元线段，也不同时研究所有的超元线段，而是再进一步优化问题的离散化，即将超元线段分组研究。如图6所示，夹在两条纵向分割边的超元线段自然地分为一组，它们的共同点是长度相同，并且端点的横坐标相同。纵向线段也可以进行类似的离散化。这样的离散化处理后，使得问题规模降低，以此为基础，算法的框架可以基本确定为：1、对平面进行分割。2、累加器ans0。3、研究每组超元线段，检测其中属于轮廓的部分的长度，并把这一长度累加入ans。4、输出ans的值。以上只是算法的基本框架，还很粗糙，求精部分有赖于数据结构的具体选择。三、Picture问题的数据结构选择之一：线性结构(一)、映射结构的建立算法的基础是问题的离散化，要进行平面“分割”，一般需要记录分割点，DABC数据结构的选择与算法效率——从IOI98试题PICTURE谈起-24-IOI’99中国集训队优秀论文选通常采用映射来记录分割点。直观的做法是采用一维数组形式，下标表示分割点的编号，数组元素表示分割点的坐标。利用下标与数组元素的自然对应，实现映射。应该说，这样表示是比较自然的，实现也比较方便。数组的优点主要是存取方便，且可以在O(NlogN)时间内排序。映射结构定义如下：TypeMapped_TYPE=ObjectLen:0..Max;{记下分割点的个数}Coord:array[1..Max]ofinteger;{记下分割点坐标}ProcedureCreat;{映射初始化}ProcedureInsert(X:integer);{插入分割坐标X}ProcedureSort;{对坐标排序}End以下是三个过程的描述与解释：ProcedureMapped_TYPE.Creat1Len0{Creat用于初始化该映射}ProcedureMapped_TYPE.Insert(X:Integer)1LenLen+12Coord[Len]X{Insert用于插入一个分割坐标，此时坐标之间是无序的}ProcedureMapped_TYPE.Sort略{Sort用于将Len个坐标排序。由于Coord是一维数组，Sort容易实现，例如快速排序。设N=Len，Sort效率可达O(NlogN)。针对整数，也可以采用筒排序得到更好的效率，但这不是问题的关键部分。}VarX_map,Y_map:Mapped_TYPE{分别记录横纵坐标的映射}以横坐标为例，在程序处理时，首先执行X_map.Creat初始化映射。而后通过X_map.Insert将每个矩形纵向边的横坐标作为分割坐标插入X_map.Coord，最后执行X_map.Sort进行排序。至此，映射建立完毕。应该说，这一部分完全可以满足算法要求，且执行效率较高。三个过程中的Creat与Insert耗时均为O(1)，Sort耗时为O(NlogN)，但它只需执行一次。(二)、线性结构的建立映射建立后，相当于完成了对平面的切割。现在的主要问题是如何描述一组超元线段的状态。由于最终要计算轮廓周长，我们最关心的是一组超元线段中究竟有多少条属于轮廓。由分组的方法可知，每组超元线段长度相同。以下均以横向超元线段为例进行说明。设：超元线段组编号1——N*2-1(N是矩形数目)IOI’99中国集训队优秀论文选-25-编号为S的超元线段组中的线段长度为Length(S)编号为S的超元线段组中属于图形轮廓的超元线段数目为Belong(S)则：其中Lenth(s)容易求得。如果超元线段组编号以网格中从左到右为原则，那么Length(s)就可以表示为：X_Map.coord[s]–X_map.Coord[s-1]，算式①只需求得Belong（s）即可。如图6，可以看到在问题的离散化之后，一组横向超元线段从上到下，数目是有限的，约有N*2条。这使得我们很容易想到线性结构。例如用一维数组来描述这么一组线段，用数组下标表示该线段从上到下的编号。数组雏形定义如下VarA:array[1..MaxSize]ofinteger基于对一维数组的使用，可以得到一个称为“累计扫描”的过程，来求解Belong(s)。累计扫描的思想是，将一维数组的元素看作计数器，计数器A[I]的内容是覆盖超元线段I的矩形上边的数目—覆盖超元线段I的矩形下边的数目。形象表示如图7：图7同时，设立累加器add，从上至下扫描超元线段，累加a[I]的值。由图7中可以看出，一条超元线段I属于轮廓的情况有两种：1、A[I]≠0且扫描到该超元线段未累加时add=0（超元线段I是矩形上边的情况）2、A[I]≠0且扫描到该超元线段累加之后add=0（超元线段I是矩形下边的情况）这样，对于一组超元线段求解Belong(s)可以分为两部分：1、对A[I]赋值，即累计过程。2、从上至下扫描一组超元线段并累加add，即扫描过程。Belong(s)的值在扫描过程中得到。至此，描述一组超元线段状态的数据结构基本确立，存储结构是线性一维数a[1]=1a[6]=-1a[4]=1a[5]=-1a[2]=1a[3]=-1add=0add=1add=2add=1add=2add=1add=012*1)(*)(NSsBelongsLength轮廓横向边周长ANS=算式①数据结构的选择与算法效率——从IOI98试题PICTURE谈起-26-IOI’99中国集训队优秀论文选组，定义的操作包括累计与扫描两个部分。定义如下：TypeGroup_TYPE=ObjectA:array[1..MaxSize]ofInteger;{线性地记录一组超元线段的信息，如图7}ProcedureCount;{累计的过程}FunctionAdding;{扫描的过程，即求解Belong(s)的过程}EndProcedureGroup_TYPE.Count{累计的过程}1数组A清零2forI1toN3doif矩形I跨越了超元线段组S{即矩形的左右边分别在线段两侧}4thenA[矩形I的上边]A[矩形I的上边]+15A[矩形I的下边]A[矩形I的下边]-1{所谓“矩形I的上边”指矩形I上边纵坐标的映射编号，“矩形I的下边”同}FunctionGroup_TYPE.Adding{扫描的过程，函数值即为Belong(S)的值}1调用Count2add03sum04forI1to纵坐标的最大映射编号5doifa[I]≠06thenifadd=07thensumsum+1{该线段是矩形的上边}8addadd+a[I]9ifadd=010thensumsum+1{该线段是矩形的下边}11returnsum{Count与Adding用于一组超元线段的累计扫描}VarScan:Group_TYPE数据结构确立后，Belong(s)通过调用Scan.Adding来计算，算式①得以实现。以上的操作针对一维数组而设计，用于进行一组超元线段的累计扫描过程。执行Scan.Adding的时间复杂度为O(N)。横向超元线段分为2*N-1组，固求解横向轮廓周长的算法时间复杂度为O(N^2)。同理，求解纵向轮廓周长的复杂度也为O(N^2)，则Picture问题的算法时间复杂度为O(N^2)。虽然这是一个多项式阶，但在最坏情况下（N接近5000时）还有一定的计算量。对数据结构选择的进一步分析累计扫描过程体现了一种认识和思维方式，以一维数组作为数据结构基础，这里是否有更好的做法，我们将作进一步分析。IOI’99中国集训队优秀论文选-27-通过求解问题对数据结构选择作的分析中，我们注意到在选择数据结构需要考虑的几个方面：1、数据结构要适应问题的状态描述。解决问题时需要对状态进行描述，在程序中，要涉及到状态的存储、转换等。选择的数据结构必需先适用