---
# System prepended metadata

title: 'ADA 6.6: Pseudo Polynomial 到底是不是多項式時間呢?'
tags: [ADA 6.6]

---

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