文档介绍：数据结构选择和算法效率——从IOI98试题PICTURE谈起
【关键字】
数据结构选择 线性结构 树形结构
【摘要】
算法 + 数据结构=程序。设计算法和选择适宜数据结构是程序设计中相辅相成两方面，缺一不可。数据结构选择一直是程序设计中关键、难点，正确地应用数据结构，往往能带来意想不到效果。反之，假如忽略了数据结构关键性，对一些问题有时就得不到满意解答。经过对IOI98试题Picture深入讨论，我们能够看到两种不一样数据结构在解题中应用，和由此得到不一样算法效率。本文以Picture问题为例，探讨数据结构选择对算法效率影响。
【正文】
引言
算法通常是决定程序效率关键，但一切算法最终全部要在对应数据结构上实现，很多算法精髓就是在于选择了适宜数据结构作为基础。在程序设计中，不仅要重视算法设计，也要正确地选择数据结构，这么往往能够事半功倍。
在算法时间和空间效率两方面，着重分析时间效率，即算法时间复杂度，因为我们总是期望程序在较短时间内给出我们所期望输出。假如在空间上过于“吝啬”而使得时间上无法承受，对解题并无益处。
本文对IOI98试题Picture作部分分析，经过两种不一样数据结构选择，将了解到数据结构对算法本身及算法效率影响。
Picture问题及算法设计
Picture问题
Picture问题是IOI98一道试题，描述以下：
墙上贴着部分海报、照片等矩形，全部边全部为垂直或水平。每个矩形能够被其它矩形部分或完全遮盖，全部矩形合并成区域边界周长称为轮廓周长。
例图1三个矩形轮廓周长为30：
图1
要求编写程序计算轮廓周长。
数据量限制：
0≤矩形数目<5000；
坐标数值为整数，范围是[-10000，10000]。
算法描述
在算法大致描述中，将不包含到具体数据结构，便于数据结构深入选择和比较分析。
、轮廓定义
在描述算法前，我们先明确一下“轮廓”定义：
1、轮廓由有限条线段组成，线段是矩形边或矩形边一部分。
2、组成矩形边线段不应被任何矩形遮盖。图2和图3分别是遮盖两种情况。
图2 图3 图4
（AB被遮盖） （CD被遮盖）
、元线段
本题一大特征是分析矩形边，而边端点（即矩形顶点）坐标为整数，且坐标取值范围已经限定在[-10000，10000]之间。这么，就能够把这个平面了解成为一个网格。因为给出坐标是整数，所以矩形边一定在网格线上。在网格中，对于一条线段我们最关心其绝对坐标。图4，我们认为矩形边AB由线段L1、L2、L3组成。像L1、L2、L3这么连接相邻网格顶点基础线段，称之为“元线段”，这么就把矩形边离散化了。显然，有限元线段覆盖了全部网格线，且元线段是组成矩形边乃至组成轮廓基础单位。一条元线段要么完全属于轮廓，要么完全不属于轮廓。这种定义使我们对问题研究具体到每一条元线段，这么离散化处理有利于问题深入讨论。
、超元线段
元线段引入，使问题愈加具体。但也应该看到，平面中共有 1* 0*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所表示，夹在两条纵向分割边超元线段自然地分为一组，它们共同点是长度相同，而且端点横坐标相同。