Tag Archives: Algorithm

演算法筆記 — 歸納法(1)

痾 . . . 歸納法是啥？沒關係，這個先別管他，來證明些數學問題吧！

現在有個理論T，而T中有一個參數n ; 我們想證明「n可以是任何自然數」的話該怎麼做呢？

最直接明瞭的方法自然就是窮舉啦 :

證明 T(n=1) 為真
證明 T(n=2) 為真
證明 T(n=3) 為真
...

可能把這串證明寫到宇宙盡頭都寫不完(❍ᴥ❍ʋ)

但是用歸納法的話只要證明兩點就好了 :

1. T(n=1)為真
2. 對所有n>1，若T(n-1)為真，則T(n)為真

KMP (Knuth-Morris-Pratt) 演算法是一個強力的字串搜尋演算法，能把原本暴力法的 O(m*n) 大刀一砍 [ 註1 ] 降成 O(m+n) !

字串搜尋，除了字面上的作用之外，在電腦科學中，還有各種應用，例如基因搜尋啦、圖像比對 [ 註2 ] 等等

回到我們的主題，每個演算法都有自己的精神，而 KMP 的精神則是 :「重複的比對不做第二次」，這也是為何 KMP 能夠將乘法時間變成加法時間的關鍵

怎麼說呢？先來看看暴力法是麼做的吧~