淺析算法分析和計算復雜性理論研究方法

楊勇杰

摘 要：近年來，我國數學領域的高速發展，使越來越多的人們認識到數學的重要性，這也使數學在各個領域中發揮著越來越重要的作用。該文淺要分析了算法及其計算復雜性，并將線性方程組中的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.