廢話不多說了～～
這是我第一堂演算法課的筆記
在講一個演算法的時候，會探討兩件事情 時間複雜度 與 空間複雜度
目前只提到了時間複雜度的部份
說簡單點就是離散數學中的Big-O
,條件為：存在正實數
和
使得對於所有的
,有
（此段轉自維基百科）
直接舉個簡單的例子好了
n^2+n = O(g(n))
n^2+n < = c g(n)
在上面這個式子之中
n^2+n 是要取BigO的式子，c與g(n) 都是可以隨意給的，只要滿足條件即可
這是其中一解
n^2+n < = 2 * n^2 when n>=0
還有其他解
n^2+n < = n^3 when n>1
所以其實是 不只一解的喔!!
不過通常會取g(n)的次方最小的
====================================================================
再來
有提到演算法的分類
polynomial V.S exponential
先解一下
polynomial 是多項式
exponential 是指數
所以簡單來說
polynomial 的演算法 就是多項式演算法
exponential 的演算法 就是指數演算法
再取Big-O之後的得出的函數是多項式時就是polynomial 的演算法
相反而言 不是多項式(有log，ｎ！之類的）就是exponential 的演算法
特例是O(1)這是常數的演算法
有了這個分類就可以區分問題
如果一個問提(題目) 有一個解法是polynomial那個問題就是easy prob
只有exponential的解法那就是NP-Complete( diffcult prob)
#注意:一個問題不只一種演算法(解法) 只要那之中有一個是polynomial就成立
這次筆記差不多就告一段落了
老師講的好理論阿~"~
這是其中一解
n^2+n < = 2 * n^2 when n>=0
還有其他解
n^2+n < = n^3 when n>1
所以其實是 不只一解的喔!!
不過通常會取g(n)的次方最小的
下面是取自維基的BIG O 常見函數
====================================================================
再來
有提到演算法的分類
polynomial V.S exponential
先解一下
polynomial 是多項式
exponential 是指數
所以簡單來說
polynomial 的演算法 就是多項式演算法
exponential 的演算法 就是指數演算法
再取Big-O之後的得出的函數是多項式時就是polynomial 的演算法
相反而言 不是多項式(有log，ｎ！之類的）就是exponential 的演算法
特例是O(1)這是常數的演算法
有了這個分類就可以區分問題
如果一個問提(題目) 有一個解法是polynomial那個問題就是easy prob
只有exponential的解法那就是NP-Complete( diffcult prob)
#注意:一個問題不只一種演算法(解法) 只要那之中有一個是polynomial就成立
這次筆記差不多就告一段落了
老師講的好理論阿~"~
沒有留言:
張貼留言