# 何謂Pseudo Polynomial?

## Polynomial v.s. Pseudo Polynomial

第一次遇到 Pseudo Polynomial 這個詞是在 0-1 knapsack problem的時間複雜度分析，若物品種類有 n 種，負重限制 W 的限制下，時間複雜度為O(nW)。
那何謂 Pseudo Polynomial ?
白話文來解釋就是：
* Polynomial:演算法之複雜度與輸入字串**長度呈多項式關係**
* Pseudo-Polynomial:演算法之複雜度與輸入數值**大小呈多項式關係**、但與輸入**數值長度呈指數關係**

也可以這樣分：(Assume 輸入數字為n)
* 如果輸入的數值，是需要針對這個數字本身去計算，那就會是Pseudo-Polynomial
* 而輸入數值代表著次數、即進行n(輸入數字這個數值)次的迭代或計算，就會屬於多項式時間

e.g. 對於 Bubble sort 來說，輸入 n 個 32-bit 數字去 sort，第一輪需要比 n-1 次 -> 針對輸入來說第一次最多要比較32(n-1)次(每個bit都要比到 least significant bit 那項)，共要 n-1 輪。

e.g. 對於輸入一個數字 n ，要判別是不是質數 -> 那就需要將輸入數值與1~sqrt(n)之區間所有數字做相除，然而輸入的數值對於電腦來說是lg n個 bits，姑且用m代表，那n就變成了2^m次，對於演算法分析時間，需要針對input length size來分析，就會變成O(2^m) 所以屬於 Pseudo Polynomial

### 如果有錯歡迎討論
---
## Reference
[https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time](https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time)
[https://www.zhihu.com/question/20013122/answer/44460397](https://www.zhihu.com/question/20013122/answer/44460397)