算法合集之《细节不可忽视的要素》

《算法合集之《细节不可忽视的要素》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、细节——不可忽视的要素广东北江中学李锐喆一、引论二、基本不影响算法时间复杂度的细节处理〖例1〗线性表维护三、影响到算法时间复杂度的细节处理〖例2〗银河英雄传说（NOI2002第一试第一题）〖例3〗铁路四、总结目录一、引论在程序设计中，算法是最核心的部分，往往一个优秀的算法能够取得比其他算法好的多的效率，但是在追求更好的算法的时候，我们往往会忽视算法中的一些细节处理。在很多时候，我们自认为用到了最优的算法，但效果往往不尽如人意，为什么呢？细节！往往是细节上的一些瑕疵，导致算法的关键地方时间效率低下，甚至导致算法的时间复杂度远远高

2、于正常的情况，最为严重的后果是导致整个算法的错误。所以，我们说，细节在程序设计中是相当重要的。借用哲学原理来说，细节是算法这个整体的关键部分，而这个关键部分往往会对算法这个整体的性能状态起决定作用。一、引论按照对算法的影响的性质和程度，我把细节分为这几种情况：基本不影响算法的时间复杂度的细节处理。这类细节处理对时间复杂度没有根本性的影响，仅仅对时间复杂度的系数产生影响。影响到算法的时间复杂度的细节处理。这类细节相当隐蔽，往往不为人所注意。但是这种细节对算法的影响相当大，处理得好与处理得不好往往会使程序的时间效率有质的区别。影响

3、到算法正确或错误的细节处理。这类细节影响最大，在竞赛中很多选手在某些题目中已经找到解决方法却不能通过全部测试数据，往往就是这类的细节处理得不当导致。一、引论第三种情况大家都肯定感受颇深，要讲的话也必然是长篇大论，这里就不再赘述了。下面，我们主要对前两种情况分别进行分析讨论。基本不影响算法的时间复杂度的细节处理。影响到算法的时间复杂度的细节处理。二、基本不影响算法时间复杂度的细节处理这类细节对算法影响不算太大，但往往在关键的时候，时间复杂度的系数的大小对算法的效率也是有比较明显的影响的。例如对于某个细节，用方法A来处理的时间复杂

4、度为　　，而方法B来处理的时间复杂度为　　（这里为了方便描述，在复杂度式中加入不需要加的系数），如果用方法A来处理整个算法的时间消耗为1s，那么用方法B来处理整个算法的时间消耗就为2s！因此，尽可能地优化细节处理，从而使算法的时间复杂度的系数降低到一个比较低的程度。下面我们通过一个例子来看看对这类细节的处理。二、基本不影响算法时间复杂度的细节处理〖例1〗线性表维护给出一个以字符串为数据类型的线性表，以及相应的若干个维护操作的规则，编写一个程序，模拟线性表的维护操作。定义一个浮动指针，指向要处理的线性表元素。定义四种对线性表的操

5、作：操作1：插入。在线性表末尾插入数据。操作2：移动指针。把浮动指针向后移若干个单位。操作3：删除。删除从浮动指针所指元素开始的若干个元素。操作4：输出。输出浮动指针所指位置的元素。请编写程序完成给出的任务。二、基本不影响算法时间复杂度的细节处理这道题目的模型很简单，由于需要动态增加、删除元素，而且空间没有限定范围，所以我们应该用动态指针来实现。插入、移动、输出这些操作都不必细说，然而对于删除操作，这里是值得我们深究的。简要的分析二、基本不影响算法时间复杂度的细节处理一般情况下，我们会用方法１来实现：每次删除元素时就把删除掉的

6、每一个元素所占的空间释放出来，等以后需要插入元素时才重新分配使用。删除的问题解决了，但是还是感到有些许不妥，那就是这样操作就是要频繁地分配和释放内存空间。释放内存空间操作的时间消耗并不大，但是分配内存空间时候由于内存空间的占用并不一定是连续的，会出现碎片的情况，因此寻找空间的时间消耗是相当可观的。有没有什么好的办法呢？二、基本不影响算法时间复杂度的细节处理那么是否可以直接利用要删除元素的空间来进行添加元素操作，而不需要分配呢？实际上这是完全可行的。于是我们有了方法2：我们不妨把线性表称之为“原链表”，然后我们另外建一个链表，称

7、之为“回收链”。我们把删除的元素放入回收链中，需要时再取出来用。删除元素要释放内存。添加元素则要分配内存。设现在我们有如下状态的原链表：下面我们具体来看一下这个方法：二、基本不影响算法时间复杂度的细节处理二、基本不影响算法时间复杂度的细节处理删除一系列元素，把它们放入回收链中。加入一个元素，直接从回收链获取空间。二、基本不影响算法时间复杂度的细节处理经过这样优化之后，实际上需要向系统提出分配内存要求的次数就是整个维护操作中链表节点数目的最大值，而通常情况下，添加节点时是从回收链中获取空间进行分配，这样进行n次添加操作的时间复杂

8、度仅仅是　　。测试点原算法优化后的算法12.149s2.012s26.588s5.672s313.202s12.924s45.086s4.911s510.297s9.918s实际测试结果测试环境：AMDDuron1.1GHz,256MBSDRAM,DebianLinux+Ke