###### tags: `ADA 6.6` # ADA 6.6: Pseudo Polynomial 到底是不是多項式時間呢? ## Pseudo Polynomial Time ### Polynomial polynomial in the **length of the input** (#bits for the input) ==定義：我考慮我input的length（假設是n），如果我的演算法是跟這個n，呈現多項式的關係的話，那我就是一個polynomial的演算法== ### Pseudo Polynomial polynomial in the **numeric value** the time complexity of 0-1 knapsack problem is $\Theta (nW)$ * $n$: number of objects * $W$: knapsack's capacity (non-negative integer) polynomial in the numeric value = pseudo-polynomial in input size = exponential inthe length of the input ==在01背包問題中，因為演算法除了跟length有關之外，又跟了一個不定的數字值w有關，所以他不能算是多項式關係，在數學中是呈現指數關係，所以我們另外把它定義為偽多項式。== ## Time Complexity Definition #### example 1 ``` function(n) for i = 1 to n print i // n is a value ``` $n=4=\underbrace{100}_{3\text{bits}}$ $n=8=\underbrace{1000}_{4\text{bits}}$ $n=16=\underbrace{1000}_{5\text{bits}}$ ==對電腦來說此時的n是$\log{n}$的關係== :::info Time Complexity: $O(n)=O(2^{\text{bits in }n})=O(2^m)$ ==此時 $m$ 才是真正的執行關係== ::: #### example 2 ``` function(a[1...n]) for i = 1 to n print a[i] // n is a length ``` $a=\underbrace{[0,1,1]}_{3}$ $a=\underbrace{[0,1,0,1]}_{4}$ $a=\underbrace{[0,1,0,1,1]}_{5}$ :::info Time Complexity: $O(n)$ ==此時 $n$ 就是真正的執行關係== ::: # Concluding Remarks * "Dynamic Programming": solve many subproblems in polynomial time for which a navie approach would take exponential time ==動態編程是指一個原本需要指數型時間的問題，可以被許多的子問題在多項式時間內解決== * When to use DP * Whether subproblem solutions can combine into the original solution ==當子問題可以被組合成原始問題的答案時== * When subproblems are **overlapping** ==可以一直重複使用之前的子問題計算的值（免去重複計算）的時候（空間換時間）== * Whether the problem has **optimal substructure** ==大問題的部分OPT也是子問題的OPT的時候== * Common for **optimization** problem ==處理最佳化問題的時候（找最大值或最小值）== * Two ways to avoid recomputation * Top-down with memoization ==不常用的，跳著填表== * Bottom-up method ==常用的，當表格的值需要全部被填上的時候，就會用== * Complexity analysis * Space for tabular filling ==考慮要填的表有多大，每一格會花多少時間== * Size of the subproblem graph ==考慮子問題的表==