杨勇杰

摘 要：近年来，我国数学领域的高速发展，使越来越多的人们认识到数学的重要性，这也使数学在各个领域中发挥着越来越重要的作用。该文浅要分析了算法及其计算复杂性，并将线性方程组中的LU分解的递归算法作为实例，以此分析算法的计算复杂性。希望能够为专家与学者在算法分析工作中提供一种科学的研究方法，进一步推动算法在各个领域中的应用。

关键词：算法分析 复杂性 理论研究 研究方法

中图分类号：TP311 文献标识码：A 文章编号：1672-3791（2019）02（b）-0234-02

1 算法介绍

从定义上来看，算法是一种具有良定义的计算过程而呈现出来的，算法中的某个或某些值可充当输入项，这些输入项还有着对应的输出项。由此可以了解到，算法的实质是将输入项按照特有的计算方式和步骤进行转换，使其成为输出项。算法作为一种解决问题的工具，能够对问题的计算过程进行良定义，以此实现对问题的准确描述，这种描述是利用输入项与输出项来进行呈现的，其对应算法则可为人们提供相应的输入输出之间的关系转换过程。

2 算法的可计算性与计算复杂性理论研究

2.1 可计算性

人们在对数学基础问题进行研究的过程中，便发现了算法的可计算性理论，该理论最早诞生于20世纪30年代。在发现该理论之前，人们为了探寻不同问题是否均有着对应的解决算法，由数理逻辑学家定义了多种不同的算法，在此背景下，递归函数概念也得以被S.C克林尼与K.哥德尔所提出，在随后的几年里，学者们又进一步证明了计算机数学模型具有相同的计算性能。可计算性理论的提出，为计算机科学的发展奠定了理论基础，自20世纪30年代起，图灵便证明了通用图灵机具有逻辑性，通过进行程序编写来制造出具有计算能力的计算机是非常可行的，这一观点对20世纪40年代的诺伊曼型计算机的设计思想产生了极为深远的影响。可计算性理论的提出，进一步明确了可用计算机进行解决的所属问题。

2.2 计算复杂性

算法所具有的计算复杂性又被称之为复杂度，计算复杂性能够对算法在计算过程中的复杂程度进行衡量，其所采用的衡量标准为算法在运行过程中所消耗的计算时间及其占用空间，其中，占用空间指的是算法在运算时所调动的存储单元数或机台数，存储单元数或机台数的调用数量越多，则占用空间越大，反之则占用空间越少。如果一个算法在运行过程中所耗费的时间及其占用的空间要少于另一个算法，则证明该算法要比另一个算法要好。可以说，算法的好坏是以时间与空间两个维度作为评价标准的，这也是算法设计人员一直以来孜孜不倦追求的目标。由此可见，算法的计算复杂性可从时间复杂性与空间复杂性两个方面来进行体现，人们在对算法所具有的特殊需要性能进行描述时，也是利用这两个方面的复杂性来评价算法的宏观质量的。

3 LU求解中递归算法分析及其计算复杂性理论研究方法

为了探寻算法的计算复杂性理论研究方法，该文以LU求解中递归算法为研究实例，以此探讨该算法复杂性。假设为线性方程组，在该方程组中，A=（aij）且、b=（b1，b2，…，bn）T。如果A为非奇异时，则该线性方程组可采取LUP进行分解，在LUP中，L代表单位下三角矩阵，而U则代表上三角矩阵，排列矩阵由P进行表示。如果P与In相等，则需要采取LU分解，分解对象为A。事实上，在进行LU分解时，其实质便是高斯消去A，也就是利用主对象线中分布的元素来对其所在列中的主对象线的元素进行相互抵消，最终使高斯消去的对象A转换成相应的上三角矩阵，即U。对于这一策略来说，可通过递归法来达到该目的，之所以要用递归法，是因为递归法相比于迭代循环法来说，其循环结构要更加实用，在递归循环结构中可非常方便地找到相应的递归关系，其最小问题的解更是能够做到一目了然。在利用递归法来进行LU求解时，其运算步骤往往只需几步，这些步骤可以對问题在求解过程中所进行的不同重复计算过程进行准确的描述，从而使算法中的代码量得以大幅减少，进而使递归算法的计算复杂性大幅降低。以下便对递归算法在线性方程线LU求解中的具体应用进行分析。

当n的值为1时，可以提前设置U与A的值相同，L与I1的值相同，此时构造完成。对于n大于1时，可以将对象A进行拆分，使其成为4个组成部分，即：

在该线性方程组中，n-1维向量由v进行表示，n-1维行向量则由wT表示，n-1阶矩阵则由A1进行表示，通过知阵代数的运用，还可以将对象A分解成以下形式，即：

在以上分解中，n-1阶矩阵便是分解后获得的，而n-1阶矩阵的表现形式是以A1-swT/a11呈现出来的，可将该矩阵用A对于a11的Schur余式来进行表示。在对Schur余式进行LU分解时，可采用递归法来进行快速寻找，命令A1-swT/a11与L1U1相等，L1U1中的L1与U1分别表示单位下三角矩阵和上三角矩阵，则可进一步分解成以下形式，即：

通过对其进一步分解，可以很方便的找到A中的LU解，如果A为对称正定时，则递归算法可始终计算下去。现如今，人们在分解矩阵中的LU时，便是依据以上所描述的递归策略来实现的，其区别在于原有的递归过程是利用迭代循环进行替代的。而在代码编写过程中，需要对A的规模进行假定，确保其存储至属性rows[A]以内，由于输出矩阵U从对角线来看，其下部元素的值都是0，而且LU-SOLVE在执行过程中并没有对上述元素进行查看，这也使这些元素没有在代码中进行填写。同样的道理，由于输出矩阵L从对角线来看，其上部所有的元素的值均等于1，而其对象线在矩阵中并没有填写这些元素，这样，需要通过相应的代码来计算输出矩阵L与U中具有代表性的元素。整个计算过程共包括10行，其中，第二行为外层for循环的开始，从该行起对各个递归步进行单次迭代。从整个循环计算过程中的第3行中可以找出主元素，即ukk=akk，从上述10行中的第四至六行中，如果k的值与n的值相等，则不执行此循环，相应的，在执行该循环时，对L与U的更新需要借助于s与wT来实现。从计算过程的第5行中，可以明确向量s中所包含的各个元素，这些元素si存储在lik内。从第六行中可以明确向量wT中所包含的各个元素，并且wTi存储在ukj以内。在整个计算过程中，第七至九行主要是对Schur余式内的所有元素进行计算，并将这些元素存储至矩阵A的各个元素以内。考虑到3层嵌套内包括第九行，因此LU-DECOMPOSITION在运行时间上由O（n3）来衡量，进而推断出该算法从本质上来看属于一种多项式时间算法。

参考文献

[1] 王继强.组合最优化与计算复杂性综述[J].电脑知识与技术，2013，9（13）：3140-3141.

[2] 李建中，李英姝.大数据计算的复杂性理论与算法研究进展[J].中国科学：信息科学，2016，46（9）：1255-1275.