20101230

生日快樂！

今天早上算了離散題庫班講義第一本的一半
進度停在中國餘數定理

心情真的很複雜...
中午前後又心浮氣躁的坐立難安
本想去睡個覺
後來乾脆把接下來要做的考古題整理出來
算是花了不少時間...
但是心情總算平靜下來了

計畫複習DS
可是這科雖然是我之前考最好的
但是卻是我最不知道怎麼準備的一科
之前是因為演算法的部份寫的還OK
不過資結的部分還是會碰到基本題寫的很抖的情況
寫了幾題分類題庫
但是DS分類題庫錯誤率實在過高
加上題目怎麼做都不是資工所的= =

所以跑去PTT看了一些前輩經驗分享
有人提到DS這科不仿提早做考古題！
所以我就直接印了88年NCTU的考題來做XD
寫的時間不多...
可是花在翻書找答案的時間卻是好幾倍作答時間！

不過也因為這樣
我剛剛鼓起勇氣的開始網NP問題邁進！
非常大的突破
因為這部份一直是我所認為的天書
也沒有勇氣去面對的一個章節
趁睡前來默寫一下好了XD

P：P集合內所包含的每一個問題均可以在多項式時間的複雜度被解決。
      即：均存在一個O(n^k)的演算法可以解決
NP：集合內所包含的每一個問題是可以在多項式時間的複雜度內被驗證(Verifiable)
         此類問題再給定一個"可能的解"情況下
         可以在多項式時間內驗證是否為"真正的解"



NP-Complete：