理論計算機作為現代計算機體系結構的一個分支，其算法與複雜性是理論計算機中最核心、最基礎的主題。下面是小編關於一些關於理論計算機算法的資料心得，與大家分享。
1. 算法
算法的出現遠遠早於計算機的出現，比如我們在小學時學過的通過列豎式的方法來計算兩個整數乘積，再比如，用著名的歐幾裡得的輾轉相除法來求兩個整數的最大公約數。很多好的算法，比如快速排序算法、高斯消元法快速傅立葉變換等，是計算機如今能在生產和生活中有如此廣泛應用的基礎。雖然算法因問題而異，但一些設計算法的方法，總會在不同的場景出現。比如貪心法、分治法、動態規劃、最大流和線性規劃等。
如何衡量一個算法的快慢或者運行時間？這是一個定義的問題。首先，算法的運行時間與運行它的機器相關，現在手機的運行能力已經遠遠超出幾十年前超級計算機的運行能力。為了解決這個問題，我們一般不直接用自然時間來衡量算法的快慢，而是用它需要進行的基本操作的數目作為時間的度量，但一般還是把它叫做運行時間。其次，算法的運行時間與問題的輸入有直接關係。一般來說，輸入的規模越大，算法的運行時間也就越長。即使是相同的輸入規模，不同的輸入所需的運行時間差異也很大。所以，如果我們在具體輸入的意義下比較不同的算法，往往得出不可比較的結論。比如算法A在輸入x上比算法B要快，但是在輸入y上則比算法B慢。因此，我們需要一個比較簡潔的量來衡量一個算法快慢。在理論計算機領域，最常用的標準是漸近意義下的最壞情況分析。我們看運行時間隨著輸入問題規模增長的函數，然後對於相同規模的不同輸入，我們考慮在該規模下最壞輸入的情況。針對這種定義方式，有很多數學上的好處，當然也有很多問題，特別是在一些特定的場合。因此，有時需要改變定義以獲得更加準確的結論，比如平滑分析等。
怎樣定義一個算法是快速有效的？它的定義是，在漸近意義下最壞情況算法的運行時間總是不超過問題輸入規模的一個多項式函數。選擇一個多項式函數的基本標準是：當問題的規模增加一倍時，其運行時間也只是常數倍增加。從數學上講，這個多項式函數類的性質應比較好。比如算法A的輸入來自算法B的結果，如果算法A、算法B都是多項式時間的，則A和B的複合函數也是多項式時間的。當然這種定義在很多時候也受到挑戰，特別是在網際網路大數據時代。因此，對於海量數據，我們需要研究在線性時間甚至亞線性時間裡，可以完成的工作種類。
2. 複雜性理論
在計算複雜性理論中，討論更多的是問題的複雜性，而不僅僅是算法的複雜性。問題的複雜性是指解決問題的最佳算法的複雜性，核心是如何確定一個問題是否存在多項式時間的算法。我們把所有存在多項式時間算法的問題定義為複雜類P，若要說明一個問題存在多項式時間的算法是比較容易的，只須給出一個這樣的算法即可；但要證明一個問題不存在任何多項式時間算法就很難，因為從原則上講，我們無法給出無窮多的算法來說明不存在的多項式時間算法。
對於NP問題，不少人會回答是Non-Polynomial，即指不存在多項式時間算法的問題。這是一個誤解，NP的N不是Non，而是Nondeterministic Turing Machine（非確定圖靈機）。NP是指所有那些在非確定圖靈機上多項式時間有解的問題。非確定圖靈機是另一個計算模型。NP問題的另一個定義是：對於這類問題，如果有一個解，則我們可以在多項式時間裡驗證該解是否正確。現實中有很多NP題，比如可滿足性問題、圖染色問題、旅行商問題等。計算複雜性領域中最核心的問題是，P類問題和NP類問題是否相等。當然，按照定義，P類問題都屬於NP，那麼是否存在NP類問題不屬於P，即不存在多項式時間算法？這是克萊研究所千禧年難題大獎中宣布的7道數學題之一（NP vs. P問題）。對於這個問題，人們普遍認為NP不等於P，但是現在看起來，我們離證明還很遙遠。複雜性理論是規約以及NP完全的理論。對此感興趣的朋友可以從教科書上找到嚴格的定義。大致來說，NP完全問題是NP問題的一個子類，也是NP問題中最難的部分。「最難」的意思是指：如果任何一個NP完全問題存在一個多項式時間的算法，那麼所有的NP問題都存在多項式時間的算法。即，如果NP不等於P，那麼任何一個NP完全問題都不存在多項式時間的算法。因為通常都相信NP不等於P，所以若要證明一個問題是NP完全的，基本上就說明這個問題是困難的。迄今為止，已經有成千上萬的問題被證明是NP完全的。除了P和NP，計算複雜性中還有很多其他複雜性類。P、NP等都是針對判定問題而言的，有些計算問題則不是判斷問題。
3. 全息算法
大多數人都相信P不等於NP，其中一個最直接的原因是已知的這些算法設計的方法都不能用來解決NP完全，或者更困難的問題。但是，為了證明P不等於NP，我們必須證明所有多項式時間的算法都不能用來解決NP完全問題。常見的算法當然不是所有的算法，而且在研究的過程中，確實會有一些新的、甚至完全不同的算法設計方法被發明。比如全息算法（Holographic Algorithm），全息算法是圖靈獎得主萊斯利教授在2004年提出的新算法設計方法，與量子計算有一些類似，但可以在經典計算機上在多項式時間內完成。萊斯利利用這項技術給一些有趣的問題設計了多項式時間算法。儘管人們很容易驗證這些算法是正確的，但並不知道如何為新問題設計全息算法。這種新算法技術吸引了一大批研究人員的注意，《科學美國人》等著名雜誌都有專題報導，大家甚至考慮這個方法是否可以解決NP問題。不過，根據學術界對全息算法的能力和局限有了完整而系統的認識，普遍認為全息算法也不能解決NP完全問題。
4. 迭代算法與局部搜索算法
對於迭代和局部搜索這類算法，其實我們也沒有很好地解釋它們為何不能解決NP完全問題。這類算法從某個初始狀態或初始解出發，不斷地按照某種規則更新當前的狀態或者解，然後達到一定的終止條件時就輸出當時的狀態或者解。典型的有解線性規劃的單純形法、機器學習中的EM算法、數值計算中的牛頓法等。這類算法的特點是其普適性，它可以適用很多不同的問題，基本上不需要巧妙的設計。當然，除了個別成功的例子外，對於這類算法的理論分析比前面提到的貪心法、動態規劃等要困難得多。
對於那些組合的算法，在同一規模的不同輸入上其運行時間大多是相對穩定的，或者至少是比較好估計、比較好預測的不同的輸入上的運行時間。對於迭代算法和局部搜索算法，它們局部狀態或者解的空間規模一般是指數級的。在這種空間上的一個迭代或者搜索能不能在多項式時間內到達終止條件呢？這是一個非常難的問題。如何從理論上更好地理解這些算法是算法理論研究中近期備受關注的一個重要方向。比如對十線性規劃的單純型法，最壞情況的運行時間是呈指數的，但它在現實中運行效果相當不錯，原因何在？斯皮爾曼（Spielman）和滕尚華提出了平滑分析（smooth analysis）的思路，並給出了解釋。其內容大致是，若那些很壞的問題實例在可能的輸人範圍內很稀疏，而且很不穩定，則只要稍微給其一些擾動，它們就能變成運行時間很短的實例。
類似這樣的算法還有很多，使用較多的有統計物理和機器學習中的基於馬爾可夫鏈的蒙特卡洛（Markov Chain Monte Carlo，MCMC）方法和信念傳播（brief propagation）算法。對於基於馬爾可夫鏈的蒙特卡洛方法，現在已經開發出許多數學工具來分析它們在何種情況下會快速到達一種穩定的分布。而我最近兩三年的一些工作就是希望利用一種相關性遞減的數學工具，來證明在一些情況下，信念傳播算法會快速收斂到正確解的一個領域。雖然我們藉助這些數學工具只能處理一部分基於馬爾可夫鏈的蒙特卡洛方法和信念傳播算法的分析，還有很多未解決的問題（對於其他迭代算法和局部搜索算法，這樣的問題就更多了），但是我認為能夠更好地理解這些算法，進而開發一些新的數學工具來分析這些算法，是當前理論計算一個非常重要的方向。這是因為它們很多時候都不是人為設計的算法，而是自然界的自然的動態規律，比如生物進化系統、社會博弈動態系統，都有這種迭代和局部調整的特點。我們開發的數學工具也可以用來分析這些動態系統。