整理资料时，发现一两年前写的一份作业，其实就是后来流产了的技术交流报告。现在看来，那时候是真够幼稚的，居然幻想着实验室的老师和同学们会花时间看，真是可笑。贴出来，博看官一笑。

----------------------------幼稚的分割线---------------------------------

算法优化对于程序的作用分析

在我们学习的过程中，要面对各种类型的实际问题。而在处理这些问题时，首先，也是最重要的就是要将它抽象为数学模型，这样才能让我们所学习的理论知识有的放矢。然后就是要设计解决问题的策略，也就是我们常说的算法。最后，要对解决问题的算法进行优化。

建模和算法设计的作用显而易见，他们是程序设计的灵魂。在建模失败的前提下，其它后续工作都是徒劳。算法设计可以使我们的程序在占用尽量小空间和花费尽量少时间的情况下解决问题。而算法优化的作用就比较模糊，有时甚至显得微不足道。

然后，实际情况并非如此。在本文中，将结合曾经做过的一个编程题目对算法优化的作用进行分析。

1 题目介绍

为了说明算法设计的思路，首先将对题目内容进行介绍。

在芯片设计过程中，每个芯片中包含多个功能模块，而各个功能模块之间有输入和输出引脚。为了实现所要设计的芯片的功能，我们要将各功能模块之间所对应的引脚连接起来。如图1所示。

图1左图表示出了两功能模块间引脚的对应关系。为了实现芯片中各功能模块的最佳布局，两功能模块引脚间连线中，最大不相交连线数目对芯片设计工程师是极为重要的。如图1右图所示，图中最大不相交连线数目为3。

本题目要完成在给出任意两模块间引脚对应关系的情况下，计算出最大不相交连线数。

2 题目分析

本题目是一个典型的DP(Dynamic Programming)问题。整个问题的解决定于其子问题的解。

首先，要将问题抽象为数学模型。在两模块间连线中，我们设左侧第1个到第i个引脚的集合与右侧第1个到第j个引脚集合间连线的最大不相交连线数为Area[i, j]。设左侧第i个引脚与右侧第j个引脚的连线数为Edge[i, j]，当两引脚中有连线时，Edge[i, j]值为1，否则为0。

通过以上分析，很容易得到该DP问题的状态转移方程：

Area[i+1, j+1]=max{Area[i, j+1], Area[i+1, j]}+Edge[i+1, j+1]

通过该状态转移方程，我们可以递归的计算出整个问题的解。

2.1 基本程序设计过程

在程序编写过程中，我们可以用循环来遍历左右引脚集合，如下式所示。将每次循环所得的结果保存在一个表中，循环结束时即可得到问题的解。

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{ …… }//n为引脚数目

对于图1中所示的情况，遍历过程及每次循环的结果如表1所示。

                                                                                                                 表1  示例

由表1所示，图1所示的情况，最大不相交连线数目为3。由于程序对于i和j进行了遍历，所以此算法为O(N²)。确立此算法后，在时间要求不是很严格的情况下，就可以得到问题的解。

2.2 算法优化

此前提到，求解该问题的基本算法为O(N²)，所以当数据量很大时，计算量和运行时间也是相当惊人的。如果仔细分析题目特征，会发现可以对其进行优化。

观察表1中所示的数据，可以发现：只有当Edge[i, j]值为1时，才能对整个表格中的数据造成影响。这一点也可以通过证明来得到。了解了这个特征，就可以对基本的算法进行优化。

每个最大不相交连线数的值在表中都对应了一个开始的位置，如在表1第4行中，值为1的最大不相交连线数开始于j为2的位置，而值为3的最大不相交连线数开始于j为3的位置。而这些值的开始位置，都是由Edge[i, j]为1的位置决定的。

根据以上分析，我们就可以设置一个表Position[t]用来保存值为t的最大不相交连线数所对应的开始位置。如在表1第1行中，Position[1]=4。在第i行中，只有一个j_i值使得Edge[i, j]为1，我们可以在1~t_max（t_max值为此刻的最大不相交连线数目）范围内将j_i与Position[t]的值进行比较，当Position[t]<j_i<Position[t+1]时，将Position[t+1]值改为j_i，并不断更新t_max的值。当遍历完每一个i值后，最后所得到的t_max即为问题的解。

对于每个i，将j_i与Position[t]的值进行比较的过程可以通过二分法查找，二分查找算法为O(logN)。所以遍历所有i的算法为O(N*logN)。与基本算法的O(N²)比较，优化后的算法有了很大的改进。用基本算法需要超过1秒的时间所解决的问题，优化后的算法只需要0.1秒就能够完成。

3 小结

在上述的例子中，我们所设计的优化方法将算法相对复杂度从O(N²)降低到O(N*logN)。这说明了在建立数学模型和基本算法设计正确的前提下，算法优化有时会对程序起至关重要的作用，尤其是在那些对算法速度、计算准确度和占用空间要求高的情况下。

文中所提到的题目请详见acm.hit.edu.cn网站上Problemset中的1288题。

附录

#include<stdio.h>

int main()

{

     int n, p, Pin[40001], Left[40001], Area[40001], i, j, left, right, middle, solution;

     scanf("%d",&n);//n为问题数量

     for(i=0;i<n;i++)

     {

          scanf("%d",&p);//p为引脚数量

          for(j=1;j<=p;j++)

          {

               scanf("%d",&Pin[j]);

               Left[Pin[j]]=j;

               Area[j]=-1;

          }

          Area[1]=Left[1];

          left=1;

          right=1;

          middle=1;

          for(j=2;j<=p;j++)

          {

               if(Left[j]<Area[left])

               {

                   Area[left]=Left[j];

                   solution=right;

               }

               else if(Left[j]>Area[right])

               {

                   right++;

                   solution=right;

                   Area[right]=Left[j];

               }

               else

               {

                    while(1)

                    {

                         middle=(left+right)/2;

                         if(Left[j]>Area[middle])

                         {

                              if(right-middle<=1)

                              {

                                   Area[right]=Left[j];

                                   break;

                              }

                              left=middle;

                         }
 
                         else if(Left[j]<Area[middle])
 
                         {

                              if(middle-left<=1)

                              {

                                   Area[middle]=Left[j];

                                   break;

                              }

                              right=middle;

                         }

                    }

               }

               left=1;

               right=solution;

          }

          printf("%d\n",solution);//solution为问题的解

      }

      return 0;

}