演算法歸納法

1. 演算法的正確性證明方法二: 結構歸納法

在上一篇文章中談到在使用循環的演算法中，可以利用 循環不變數 證明演算法的正確性，那如果是使用遞歸的演算法呢。

遞歸的演算法在計算中會形成某種 遞歸結構 ，因此可以利用結構歸納法來證明正確性。

看到這個名字，我們會自然想起 數學歸納法 。
其實它是數學歸納法的一般化，也就是說數學歸納法是它的特殊化。

它用於證明，某種遞歸結構 x（list or tree）滿足命題 P (x)，證明方法類似我們熟悉的數學歸納法。
首先提出一個命題 P (x)，證明 最小結構 和 子結構 均滿足命題 P (x)，那麼這種遞歸結構滿足命題 P (x)。

而這個命題經過結構歸納法證明後，能用作證明相應演算法的正確性。

跟上一篇一樣，我們使用 歸並排序（Merge sort） 作為例子，不過這次用到的是它的遞歸函數。

了解歸並排序的朋友會知道它使用了 分治法
分治法的中心思想是把問題 遞歸 分割為子問題，一直到不能繼續 分割 的最小子問題（base case），最小子問題的解決方法很簡單明顯，這時遞歸返回並將子問題的答案逐層 合並 ，最後就是原問題的答案了。

歸並排序的 3 個步驟分別如下：

假設原數組為 [ 5 2 4 7 1 3 2 6 ] ，它在 分割 階段呈現以下的二叉樹結構

首先提出命題

然後使用結構歸納法證明：

因此當二叉樹高度為最大值時，已遞歸分割至最底層（數組大小為1不能繼續分割），停止遞歸並將子問題答案通過 merge 函數合並逐層返回，而 merge 函數在 上一篇 中已證明其正確性，因此歸並排序演算法的正確性得以證明。

2. 演算法設計與分析歸納法需要哪兩個步驟

總結演算法設計的步驟

• 弄清楚題目的意思，列出題目的輸入、輸出、約束條件

• 思考怎樣讓演算法的時間復雜度盡可能的小

• 編寫偽代碼或代碼

歸納思維

• 是從特殊情況出發

• 推理出一般性的結論

• 作為數據分析的重要思維，應該引起足夠的重視。

擴展：介紹 5 種歸納方法，即：求同法、求異法、共用法、共變法和剩餘法，其實這些方法早在古代就有，後來培根在《新工具》一書中進行了概括和歸納，最後由穆勒加以系統的整理和說明，因此通常稱為「穆勒五法」。

3. 計算機二級數據結構與演算法知識點

一、數據結構

（1）數據結構的基本概念

1、數據：數據是客觀事物的符號表示，是能輸入到計算機中並被計算程序識別和處理的符號的總稱，如文檔，聲音，視頻等。

2、數據元素：數據元素是數據的基本單位。

3、數據對象：數據對象是性質相同的數據元素的集合。

4、數據結構：是指由某一數據對象中所有數據成員之間的關系組成的集合。

（2）邏輯結構和存儲結構

1、數據結構可分為數據的邏輯結構和存儲結構。

1）數據的邏輯結構是對數據元素之間的邏輯關系的描述，與數據的存儲無關，是面向問題的，是獨立於計算機的。它包括數據對象和數據對象之間的關系。

2）數據的存儲結構也稱為數據的物理結構，是數據在計算機中的存放的方式，是面向計算機的，它包括數據元素的存儲方式和關系的存儲方式。

2、存儲結構和邏輯結構的關系：一種數據的邏輯結構可以表示成多種存儲結構即數據的邏輯結構和存儲結構不一定一一對應。

3、常見的存儲結構有：順序，鏈接，索引等。採用不同的存儲結構其數據處理的效率是不同的。

4. C語言裡面的演算法覺得很難,這樣才能學好演算法

學好C語言首先要學好他的語法，就比如說英語和語文，你必須要學好他的語法啊，並且要會用他的」單詞」，然後就是演算法了，這其中要有數學的計算和思想，但是你可以學好的，如果你學好VB那就更好了，因為VB和C語言、很都語法都是共通的．C重要的是思想和演算法．．
如果要成為高手的話，那就必須數學基礎扎實，因為要到高級的話會用到很多的函數問題，編程也要邏輯性好，而且C就是一種模式，找到了很容易學的。
說實在的，有些東西當初我拿到書的時候是天天琢磨，月月思考，還真別說，有些當初我以為超級老難的問題就愣是這么給琢磨出來了。不過前提是我的數學和邏輯思維真的不錯。
慢慢來啊，呵呵，就像當初我以為我自己也學不會，結果還是讓我給征服了。其實入門比較困難一些，這都是過程，保持好的心態，如果真的想學就不要放棄，經過時間的積累我想一切都會晴朗的。

5. 如何用歸納法證明演算法的時間復雜度 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的取值什麼的。如果這題目正常的話就應該會的出值了。

6. 數學歸納法中增乘怎麼算

即n=1×2×3×...×（n-1）×n。數學歸納法增乘演算法公式為，即n=1×2×3×...×（n-1）×n，階乘亦可以遞歸方式定義：n=1，n=（n-1）×n，該演算法是全日制高級中學教科書《數學》第三冊內容。