算法分析

杨利霞

5 D# K* G* w9 {

算法分析

  N2 t) C" @: j/ e8 D; M

2010年东北三省联赛算法分析及建模过程表述

算法分析：

由于同一个问题可以用不同的算法实现，且不同的算法有不同的执行效率，这些差异甚至可以影响整个程序的执行效率，所以我们要对算法作复杂性，可行性和误差的分析。对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，在这一步上我们分别运用了反证法及构造函数法证明了算法在数学上的逻辑性及推理的严密性，将问题成功给转化为整数规划的模型，并且引入0—1变量，在简化算法及模型的软件实现上得到了较大的优化。而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。而具体就本题而言，在算法复杂性的考量上我们不妨从以下三个方面来分析：1.执行算法所耗费的时间；2.执行算法所耗费的存储空间，其中主要考虑辅助存储空间；3.算法应易于理解，易于编码，易于调试等等。

时间复杂性和空间复杂性都是算法要解决问题的规模和算法输入的函数，然而对于输入规模不是很好下定义，非严格的讲，输入规模是指算法所接受输入的自然独立体的大小。例如，对于排序算法来说，输入规模一般就是待排序元素的个数，而就本题来看，我们不妨将输入规模可以看作是单个方阵的维数。本题中我们使用LINGO软件来辅助求解，相应的有两个程序PRG_1、PRG_2。在空间复杂度的考察上，根据我们实际操作的结果，我们得出整个模型总共涉及302个变量，迭代16977步，在内存中占用的总使用量仅为115k，运算时间仅为2秒。说明经过假设分区来简化的本模型算法复杂度是较低的。

0 u- \0 H" `0 f* F( ?" q% J: p$ v) }