證明演算法的

『壹』 怎麼證明由三種基本結構所構成的演算法可以解決任何復雜問題

三種基本結構化結構：順序、選擇、循環。證明如下：

一、很多書籍確確實實的說明指出，這三種結構可以解決一切復雜的演算法問題是已經證明了的。

二、演算法過程就是一個步驟一個步驟、一條指令一條指令按照程序執行的過程，所以順序結構很自然的就是演算法的一個最基本的特性。

三、我們在解決問題時，由於對一些事實情況把握不太確定（邏輯學告訴我們思維必須確定才能進行正確的思維，否則會發生前後矛盾的情況，這也是一個良好演算法的要求），所以如果不進行正確的判斷的話，就不能輕易進入下一步驟。

由此當演算法執行到某一步驟時，如果要對某些情況進行判斷，才能進入下一步的執行，那麼選擇結構就是必須的了。它正是判斷了之後，再確定該執行哪些步驟。

四、循環結構是非必需的，它可有前兩種結構構成。

所以，總結起來：任何演算法它都是機械的一系列步驟，並且要求每一步都是確定的，當執行完這一步驟後，它就要確定下一步驟，如果根據演算法對象已經知道下一步該執行什麼了，就不需要再判斷直接進入下一步。

但是當對這些演算法對象的情況不確定時，我們就要判斷並選擇一些已經確定好操作對象的步驟。這也是問題的一個最根本的特性，就是我們提出問題的原因。因為思維遇到阻礙，就需要判斷，只有確定後才能繼續正確思維，才能解決問題。

『貳』 演算法的正確性證明方法一: 循環不變數

在之前的一篇文章里寫到 演算法的正確性 的概念以及它的作用，下面就來寫寫循環不變數在演算法的正確性證明中的用法。

在使用循環的演算法里，可以通過循環不變數證明其正確性。
所謂循環不變數是指一種在整個循環過程中保持不變的性質，它必須在以下3種情況下均保持不變，且該性質源困在循環終止後能證明演算法的正確性。

接下來就 歸並排序（Merge sort） 中的 merge 函數來說明一下循環不變數

先解釋一下這個函數的作用，sld 和 srd 為已排序數組，大小分別為 lc 和 rc，循環 tc (lc + rc) 次把它們的元素進行比較並復制到新分配的數組 md 中，那要怎麼證明這個演算法的正確性呢。

讓我們先設定循環不變數，然後看8-18行的循環能否在以上3種情況都滿足這個循環不變數。

結束時循環不變數給了我們一個有用信息，此遲氏時 md 已經把 sld 和 srd 中全部元素合並排序了， 從雹旦念而證明了演算法的正確性。

『叄』 如何用歸納法證明演算法的時間復雜度 t(n)<=T(n/5)+T(3n/4)+cn<=20cn

1.假設n=1時候，驗證
t(1)<=T(1/5)+T(3/4)+c<=20c
2.假設當n=k-1（或者n<=k-1，這兩個具體情況具體分析)時候滿足：
t(k-1)<=T(k-1/5)+T(3(k-1)/4)+c(k-1)<=20c(k-1)
當n=k時候，
從各個方面分析,t(k-1)與t(k)d的關系，T(k-1)與T(k)的關系，以及c的取值什麼的。如果這題目正常的話就應該會的出值了。

『肆』 貪心演算法的證明方法

貪心演算法的基本思路如下：
1.建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優解。
4.把子問題的解局部最優解合成原來解問題的一個解。
----------------------------------------------
其實歸納起來也就一個類。其他的都是分支

『伍』 圖論演算法的論證

有向無迴路圖又稱為dag。對這種有向無迴路圖的拓撲排序的結果為該圖所有頂點的一個線性序列，滿足如果G包含(u,v)，則在序列中u出現在v之前（如果圖是有迴路的就不可能存在這樣的線性序列）。一個圖的拓撲排序可以看成是圖的所有頂點沿水平線排成的一個序列，使得所有的有向邊均從左指向右。因此，拓撲排序不同於通常意義上對於線性表的排序。
有向無迴路圖經常用於說明事件發生的先後次序，圖1給出一個實例說明早晨穿衣的過程。必須先穿某一衣物才能再穿其他衣物（如先穿襪子後穿鞋），也有一些衣物可以按任意次序穿戴（如襪子和短褲）。
圖中說明經拓撲排序的結點以與其完成時刻相反的順序出現。因為深度優先搜索的運行時間為θ(V+E)，每一個v中結點插入鏈表需佔用的時間為θ(1)，因此進行拓撲排序的運行時間θ(V+E)。
為了證明演算法的正確性，我們運用了下面有關有向無迴路圖的重要引理。 有向圖G無迴路當且僅當對G進行深度優先搜索沒有得到反向邊。
證明：→：假設有一條反向邊(u,v)，那麼在深度優先森林中結點v必為結點u的祖先，因此G中從v到u必存在一通路，這一通路和邊(u,v)構成一個迴路。
←：假設G中包含一迴路C，我們證明對G的深度優先搜索將產生一條反向邊。設v是迴路C中第一個被發現的結點且邊(u,v)是C中的優先邊，在時刻d[v]從v到u存在一條由白色結點組成的通路，根據白色路徑定理可知在深度優先森林中結點u必是結點v的後裔，因而(u,v)是一條反向邊。（證畢） Topological_Sort(G)演算法可產生有向無迴路圖G的拓撲排序
證明
假設對一已知有問無迴路圖G=(V,E)運行過程DFS以確定其結點的完成時刻。那麼只要證明對任一對不同結點u,v∈V，若G中存在一條從u到v的有向邊，則f[v]<F[U]即可。考慮過程DFS(G)所探尋的任何邊(U,V)，當探尋到該邊時，結點V不可能為灰色，否則V將成為U的祖先，(U,V)將是一條反向邊，和引理1矛盾。
因此，v必定是白色或黑色結點。若v是白色，它就成為u的後裔，因此f[v]<F[U]。若V是黑色，同樣F[V]<F[U]。這樣一來對於圖中任意邊(U,V)，都有F[V]<F[U]，從而定理得證。（證畢）