理论计算机初步：概率算法和近似算法
所以人們發展了各種工具來避開它們，最常用的兩種方法是使用概率算法和近似算法，這兩種方法也符合實際需要：在解決實際問題中，我們不需要結果絕對正確，也不需要結果絕對精確。
所謂概率算法，就是在算法的過程中引入隨機數，使得算法在執行的過程中隨機選擇下一個計算步驟。它最后可能導致結果也是不確定的。一個結果不確定的概率算法叫做Monte Carlo算法，而總是得到準確解的概率算法叫做Sherwood算法（一個例子是引進隨機因子的快速排序算法）。
為何引入隨機數能夠提升計算性能（事實上，理論計算機學家還沒能證實隨機因子本質上更有效率——指具有指數級別的效率提升），主要有下面兩個原因：
首先，通常一個算法，它對于很多種情況是比較快的，但對于某些「特別差」的輸入，它要找到一個解則特別困難。引入隨機數之后，使得算法的時間復雜度平均化了，然后算得更快（評價一個隨機算法的復雜性通常是考慮其平均復雜性）。
其次，對于Monte Carlo算法，它的輸出是不精確的，這種犧牲使得算法能夠在較短時間內完成。
需要指出的是，下面這個定理，使得一個不那么精確的Monte Carlo算法亦有實際的效用的：
如果一個判定問題的某個Monte Carlo算法有2/3的正確幾率(這個2/3可以替換成任何一個大于1/2的數，當然小于等于1/2的隨機算法一點意義都沒有，因為還不如拋硬幣)，重復這個算法k次，取出現次數更多的結果作為問題的答案，則這個答案的正確率大于1-1/2(8/9)^k。
上面的結果由于k出現在指數上，所以只需要將一個Monte Carle算法重復很少的次數，便能得到很高的準確率。
近似算法從字面的意思來看似乎和上面的Monte Carle算法差不多，其實它們的考慮對象是不一樣的，而且通常所指的近似算法是確定型算法。近似算法多用在組合優化的問題，而不是判定性問題上。組合優化問題，指的是那些需要求最優解的問題，比如下面這個
旅行商問題
有n個城市，一個推銷員要從其中某一個城市出發，不重復地走遍所有的城市，再回到他出發的城市。問這個推銷員的最短路程。
對于這種問題，如果最短路徑是1000，而且我們能很快找到一個1000.1的路徑，在實際運用中，我們還需要浪費巨大的計算資源去找那個1000的路徑嗎？近似算法便基于此思想而來。
近似算法指在解決優化問題中，最后得到的結果能保證在一定的誤差之內的算法。
從近似算法的角度來說，同為NP完全問題，它們也有不同的可近似度。在多項式時間內，有些問題可以無窮小誤差的逼近，但有些問題卻連常數倍數之內的結果都沒法得到。
總結
以上是生活随笔為你收集整理的理论计算机初步：概率算法和近似算法的全部內容，希望文章能夠幫你解決所遇到的問題。
