淺析算法分析和計(jì)算復(fù)雜性理論研究方法

楊勇杰

摘 要：近年來，我國數(shù)學(xué)領(lǐng)域的高速發(fā)展，使越來越多的人們認(rèn)識到數(shù)學(xué)的重要性，這也使數(shù)學(xué)在各個(gè)領(lǐng)域中發(fā)揮著越來越重要的作用。該文淺要分析了算法及其計(jì)算復(fù)雜性，并將線性方程組中的LU分解的遞歸算法作為實(shí)例，以此分析算法的計(jì)算復(fù)雜性。希望能夠?yàn)閷＜遗c學(xué)者在算法分析工作中提供一種科學(xué)的研究方法，進(jìn)一步推動(dòng)算法在各個(gè)領(lǐng)域中的應(yīng)用。

關(guān)鍵詞：算法分析 復(fù)雜性 理論研究 研究方法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2019）02（b）-0234-02

1 算法介紹

從定義上來看，算法是一種具有良定義的計(jì)算過程而呈現(xiàn)出來的，算法中的某個(gè)或某些值可充當(dāng)輸入項(xiàng)，這些輸入項(xiàng)還有著對應(yīng)的輸出項(xiàng)。由此可以了解到，算法的實(shí)質(zhì)是將輸入項(xiàng)按照特有的計(jì)算方式和步驟進(jìn)行轉(zhuǎn)換，使其成為輸出項(xiàng)。算法作為一種解決問題的工具，能夠?qū)栴}的計(jì)算過程進(jìn)行良定義，以此實(shí)現(xiàn)對問題的準(zhǔn)確描述，這種描述是利用輸入項(xiàng)與輸出項(xiàng)來進(jìn)行呈現(xiàn)的，其對應(yīng)算法則可為人們提供相應(yīng)的輸入輸出之間的關(guān)系轉(zhuǎn)換過程。

2 算法的可計(jì)算性與計(jì)算復(fù)雜性理論研究

2.1 可計(jì)算性

人們在對數(shù)學(xué)基礎(chǔ)問題進(jìn)行研究的過程中，便發(fā)現(xiàn)了算法的可計(jì)算性理論，該理論最早誕生于20世紀(jì)30年代。在發(fā)現(xiàn)該理論之前，人們?yōu)榱颂綄げ煌瑔栴}是否均有著對應(yīng)的解決算法，由數(shù)理邏輯學(xué)家定義了多種不同的算法，在此背景下，遞歸函數(shù)概念也得以被S.C克林尼與K.哥德爾所提出，在隨后的幾年里，學(xué)者們又進(jìn)一步證明了計(jì)算機(jī)數(shù)學(xué)模型具有相同的計(jì)算性能。可計(jì)算性理論的提出，為計(jì)算機(jī)科學(xué)的發(fā)展奠定了理論基礎(chǔ)，自20世紀(jì)30年代起，圖靈便證明了通用圖靈機(jī)具有邏輯性，通過進(jìn)行程序編寫來制造出具有計(jì)算能力的計(jì)算機(jī)是非?？尚械?，這一觀點(diǎn)對20世紀(jì)40年代的諾伊曼型計(jì)算機(jī)的設(shè)計(jì)思想產(chǎn)生了極為深遠(yuǎn)的影響?？捎?jì)算性理論的提出，進(jìn)一步明確了可用計(jì)算機(jī)進(jìn)行解決的所屬問題。

2.2 計(jì)算復(fù)雜性

算法所具有的計(jì)算復(fù)雜性又被稱之為復(fù)雜度，計(jì)算復(fù)雜性能夠?qū)λ惴ㄔ谟?jì)算過程中的復(fù)雜程度進(jìn)行衡量，其所采用的衡量標(biāo)準(zhǔn)為算法在運(yùn)行過程中所消耗的計(jì)算時(shí)間及其占用空間，其中，占用空間指的是算法在運(yùn)算時(shí)所調(diào)動(dòng)的存儲(chǔ)單元數(shù)或機(jī)臺(tái)數(shù)，存儲(chǔ)單元數(shù)或機(jī)臺(tái)數(shù)的調(diào)用數(shù)量越多，則占用空間越大，反之則占用空間越少。如果一個(gè)算法在運(yùn)行過程中所耗費(fèi)的時(shí)間及其占用的空間要少于另一個(gè)算法，則證明該算法要比另一個(gè)算法要好?？梢哉f，算法的好壞是以時(shí)間與空間兩個(gè)維度作為評價(jià)標(biāo)準(zhǔn)的，這也是算法設(shè)計(jì)人員一直以來孜孜不倦追求的目標(biāo)。由此可見，算法的計(jì)算復(fù)雜性可從時(shí)間復(fù)雜性與空間復(fù)雜性兩個(gè)方面來進(jìn)行體現(xiàn)，人們在對算法所具有的特殊需要性能進(jìn)行描述時(shí)，也是利用這兩個(gè)方面的復(fù)雜性來評價(jià)算法的宏觀質(zhì)量的。

3 LU求解中遞歸算法分析及其計(jì)算復(fù)雜性理論研究方法

為了探尋算法的計(jì)算復(fù)雜性理論研究方法，該文以LU求解中遞歸算法為研究實(shí)例，以此探討該算法復(fù)雜性。假設(shè)為線性方程組，在該方程組中，A=（aij）且、b=（b1，b2，…，bn）T。如果A為非奇異時(shí)，則該線性方程組可采取LUP進(jìn)行分解，在LUP中，L代表單位下三角矩陣，而U則代表上三角矩陣，排列矩陣由P進(jìn)行表示。如果P與In相等，則需要采取LU分解，分解對象為A。事實(shí)上，在進(jìn)行LU分解時(shí)，其實(shí)質(zhì)便是高斯消去A，也就是利用主對象線中分布的元素來對其所在列中的主對象線的元素進(jìn)行相互抵消，最終使高斯消去的對象A轉(zhuǎn)換成相應(yīng)的上三角矩陣，即U。對于這一策略來說，可通過遞歸法來達(dá)到該目的，之所以要用遞歸法，是因?yàn)檫f歸法相比于迭代循環(huán)法來說，其循環(huán)結(jié)構(gòu)要更加實(shí)用，在遞歸循環(huán)結(jié)構(gòu)中可非常方便地找到相應(yīng)的遞歸關(guān)系，其最小問題的解更是能夠做到一目了然。在利用遞歸法來進(jìn)行LU求解時(shí)，其運(yùn)算步驟往往只需幾步，這些步驟可以對問題在求解過程中所進(jìn)行的不同重復(fù)計(jì)算過程進(jìn)行準(zhǔn)確的描述，從而使算法中的代碼量得以大幅減少，進(jìn)而使遞歸算法的計(jì)算復(fù)雜性大幅降低。以下便對遞歸算法在線性方程線LU求解中的具體應(yīng)用進(jìn)行分析。

當(dāng)n的值為1時(shí)，可以提前設(shè)置U與A的值相同，L與I1的值相同，此時(shí)構(gòu)造完成。對于n大于1時(shí)，可以將對象A進(jìn)行拆分，使其成為4個(gè)組成部分，即：

在該線性方程組中，n-1維向量由v進(jìn)行表示，n-1維行向量則由wT表示，n-1階矩陣則由A1進(jìn)行表示，通過知陣代數(shù)的運(yùn)用，還可以將對象A分解成以下形式，即：

在以上分解中，n-1階矩陣便是分解后獲得的，而n-1階矩陣的表現(xiàn)形式是以A1-swT/a11呈現(xiàn)出來的，可將該矩陣用A對于a11的Schur余式來進(jìn)行表示。在對Schur余式進(jìn)行LU分解時(shí)，可采用遞歸法來進(jìn)行快速尋找，命令A(yù)1-swT/a11與L1U1相等，L1U1中的L1與U1分別表示單位下三角矩陣和上三角矩陣，則可進(jìn)一步分解成以下形式，即：

通過對其進(jìn)一步分解，可以很方便的找到A中的LU解，如果A為對稱正定時(shí)，則遞歸算法可始終計(jì)算下去。現(xiàn)如今，人們在分解矩陣中的LU時(shí)，便是依據(jù)以上所描述的遞歸策略來實(shí)現(xiàn)的，其區(qū)別在于原有的遞歸過程是利用迭代循環(huán)進(jìn)行替代的。而在代碼編寫過程中，需要對A的規(guī)模進(jìn)行假定，確保其存儲(chǔ)至屬性rows[A]以內(nèi)，由于輸出矩陣U從對角線來看，其下部元素的值都是0，而且LU-SOLVE在執(zhí)行過程中并沒有對上述元素進(jìn)行查看，這也使這些元素沒有在代碼中進(jìn)行填寫。同樣的道理，由于輸出矩陣L從對角線來看，其上部所有的元素的值均等于1，而其對象線在矩陣中并沒有填寫這些元素，這樣，需要通過相應(yīng)的代碼來計(jì)算輸出矩陣L與U中具有代表性的元素。整個(gè)計(jì)算過程共包括10行，其中，第二行為外層for循環(huán)的開始，從該行起對各個(gè)遞歸步進(jìn)行單次迭代。從整個(gè)循環(huán)計(jì)算過程中的第3行中可以找出主元素，即ukk=akk，從上述10行中的第四至六行中，如果k的值與n的值相等，則不執(zhí)行此循環(huán)，相應(yīng)的，在執(zhí)行該循環(huán)時(shí)，對L與U的更新需要借助于s與wT來實(shí)現(xiàn)。從計(jì)算過程的第5行中，可以明確向量s中所包含的各個(gè)元素，這些元素si存儲(chǔ)在lik內(nèi)。從第六行中可以明確向量wT中所包含的各個(gè)元素，并且wTi存儲(chǔ)在ukj以內(nèi)。在整個(gè)計(jì)算過程中，第七至九行主要是對Schur余式內(nèi)的所有元素進(jìn)行計(jì)算，并將這些元素存儲(chǔ)至矩陣A的各個(gè)元素以內(nèi)?？紤]到3層嵌套內(nèi)包括第九行，因此LU-DECOMPOSITION在運(yùn)行時(shí)間上由O（n3）來衡量，進(jìn)而推斷出該算法從本質(zhì)上來看屬于一種多項(xiàng)式時(shí)間算法。

參考文獻(xiàn)

[1] 王繼強(qiáng).組合最優(yōu)化與計(jì)算復(fù)雜性綜述[J].電腦知識與技術(shù)，2013，9（13）：3140-3141.

[2] 李建中，李英姝.大數(shù)據(jù)計(jì)算的復(fù)雜性理論與算法研究進(jìn)展[J].中國科學(xué)：信息科學(xué)，2016，46（9）：1255-1275.