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

$\mathrm{\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=\underset{3\text{bits}}{\underbrace{100}}$

$n=8=\underset{4\text{bits}}{\underbrace{1000}}$

$n=16=\underset{5\text{bits}}{\underbrace{1000}}$

對電腦來說此時的n是

$\log n$的關係

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=\underset{3}{\underbrace{[0,1,1]}}$

$a=\underset{4}{\underbrace{[0,1,0,1]}}$

$a=\underset{5}{\underbrace{[0,1,0,1,1]}}$

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
    考慮子問題的表