重念一次早該補起來的「資料結構與演算法」。這篇筆記下 P 與 NP 問題簡介。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/30004
本篇範圍：Chapter 13
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
P：指所有可在多項式時間內解決的問題
NP：是所有可在多項式時間內驗證解的正確性的問題
1. 若一個問題的解很容易去確認其正確性，代表此問題可以快速解出嘛？ < P v.s. NP 問題 >
2. 有些問題的解是可以解，但花費的時間卻非常的長 ( 像是 N 皇后問題，其問題所有解所需時間難度，會呈指數成長)
3. 有可能找到一個快速的演算法 ( polynomial time ) 來解決這些 NP 問題嘛？存在這樣的演算法嘛？
經典問題
相當大的數字 (如 200 位 ) 是由兩個質數相乘而得，那這兩個質數分別是多少？
你要找到一個有效率的演算法來解，目前是沒有的。不過若你要判別某一個質數是不是可整除這個大數，那所花的時間還是在可預期的範圍 ( polynomial time ) 的
