---
title: 2020FMath203 Week5
tags: 2020F, Math203
---
----
## 5: 演算法複雜度 (2020/10/04~2020/10/10)
週五國慶日補假
---
### 這週要做的事
#### 影片（每週二上課前完成）
- [video 5](https://www.youtube.com/watch?v=RQ06EzCPk_I): Big Oh and Little Oh
- reading assignment: [4.3 The Big "Oh" and Little "Oh" Notations](https://rellek.net/book/s_basics_big-oh.html)
- [questions 5](https://docs.google.com/forms/d/e/1FAIpQLSdPgQwLVPttpzQsZoJc8oB5Oix7s6tTZNyWDqBS9huCBemKPA/viewform?usp=sf_link)
```
AL 分數 += Question 分數 * 0.01
```
[//]: # (
scalar doesn't mater, time doesn't mater
O and o
scale
)
#### HW5（下週二 5:00 pm 前交給助教）
請註明姓名學號以及第幾次作業
1. 證明對任意 $\epsilon > 0$ 而言， $\ln(n) = o(n^\epsilon)$ 都成立。證明對任意 $K > 0$ 而言， $n^K = o(e^n)$ 都成立。
2. 證明
$$\binom{2n}{n} = \binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2$$
---
### Big Oh and Little Oh
- Kahoot: [Big Oh and Little Oh](https://create.kahoot.it/share/76167c4f-908a-498b-96e4-4132c0e257a0)
若 $f:\mathbb{N}\rightarrow\mathbb{R}_{\geq 0}$ 和 $g:\mathbb{N}\rightarrow\mathbb{R}_{\geq 0}$ 為兩函數。
如果存在 $c>0$ 及 $n_0>0$ 使得 $f(n) \leq cg(n)$ whenever $n\geq n_0$，則我們說 $f = O(g)$（讀作 $f$ 是 "Big Oh of" $g$）
如果
$$\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=0$$
，則我們說 $f = o(g)$（讀作 $f$ 是 "Little oh of" $g$）
[//]: # (10 T or F questions)
---
### 用 Python 畫圖
[Example](https://sagecell.sagemath.org/?z=eJxFzMsKwyAQheG9TzE7L4ho93kYQ4ZUGC8YQ83bV5tCdsP5PybEkmuDdMZygT8gFRbuKfpWKDcKqynXvGYu1BjrsAxnfPVpR-G0s04yNpKZTFhjHSjoSr008Iob10B-RVr4L83A5eP7UCud-LDO__8Id0ybuPHxzh8hv-ujNsA=&lang=sage&interacts=eJyLjgUAARUAuQ==) on SageCell
```python
import numpy as np
import matplotlib.pyplot as plt
x = np.arange(1,101)
plt.plot(0.01 * x**2, 'red', label='0.01 x**2')
plt.plot(x, 'blue', label='x')
plt.legend()
plt.show()
```
---
### 估計
令 $\pi(n)$ 為 $n$ 以下質數的個數。
比如說 $10$ 以下的質數有 $2,3,5,7$，所以 $\pi(10) = 4$ 而 $\pi(11) = 5$。
- 計算一下 $\pi(100)$ 及 $\pi(200)$。
```python
n = 100
count = 0
for i in range(1, n+1):
if is_prime(i):
count += 1
#print(i)
print(count, N(n/log(n)))
```
$\pi(n)$ 沒有確切的公式，但是有人證明 $\pi(n)$ 大概跟 $\frac{n}{\ln n}$ 差不多。
##### Theorem (Prime Number Theorem)
令 $\pi(n)$ 為 $n$ 以下質數的個數。則
$$\lim_{n\rightarrow\infty}\frac{\pi(n)\ln(n)}{n} = 1.$$
---
### P = NP？
考慮一個計算問題，它的計算時間跟輸入大小 $n$ 有關。
如果這個問題有演算法可以在 $O(n^c)$ 的時間內回答出來，則我們說這是一個 **P 問題**。這樣的演算法我們稱為 **polynomial time algorithm**。比如說：
> 判斷一個長度為 $n$ 的數列是否為嚴格遞增。
有一些問題，看起來很難，像是
> 分堆問題：輸入 $n$ 個整數，判斷這些整數是否可以分成總和一樣的兩堆。
乍看之下這個問題要 $2^{n-1}$ 的時間才能回答。然而如果天上突然掉下來一張紙，上面寫著分堆的方法（certificate），則只要在 $O(n^c)$ 的時間內就可以回答答案為**是**。
所以看起來好像只是人類太蠢，還沒找到好的演算法來回答這個問題，而不是這個問題太難。如果一個問題存在多項式時間可以驗證的 certificate，來驗證答案為是，則這樣的問題稱作 **NP 問題**。
顯然任何 P 問題都存在這樣的 certificate，所以任何 P 問題都是 NP 問題。
##### Conjecture
P $!=$ NP？
判斷以下的問題屬於哪一類？ P、NP、都不是？
- 判斷一個長度是 $n$ 的字串中是否有至少三個 $0$。
- 判斷 $n$ 個整數中是否有三個整數總和為 $100$。
- 判斷一個長度為 $n$ 的數列是否存在長度為 $3$ 的遞增子數列。
- 判斷 $1,\ldots,10000$ 中質數的個數是否大於 $500$ 個。
- 判斷一個 $n$ 位正整數是否可以被 $m$ 位正整數整除 ($n\geq m$)。
- 判斷一個 $n$ 位正整數是否為質數。
- 判斷 $n$ 個數字中是否有一個子集其總合為 $0$。
---
### Summary: 證明組合等式
回顧一下這些等式的證明。
組合證明：
$$\sum_{k=1}^n 2k-1 = n^2$$
double counting：
$$\binom{n}{0}2^n + \binom{n}{1}2^{n-1} + \cdots + \binom{n}{n}2^0 = 3^n $$
數學歸納法：
$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$
---
### Summary: 除法原理
證明對於任意奇數 $n$，$n$ 和 $2n + 4$ 一定互質。
找出一對整數 $a,b$ 使得 $7a + 11b = 5$。
---
### Summary: 鴿籠原理
證明從 $\{1,\ldots,100\}$ 中任取 $51$ 個數字，一定有其中兩個數字互質。
證明從 $\{1,\ldots,100\}$ 中任取 $51$ 個數字，一定有兩個數字總和為 $101$。
證明從 $\{1,\ldots,100\}$ 中任取 $51$ 個數字，一定有一個數字整除另一個。
六個人之中，有的互相認識有的互相不認識，證明一定有兩個人認識的人數是一樣的。
---
### Summary: 演算法
記得 $O(g)$ 和 $o(g)$ 的意思嗎？
有可能 $f=O(g)$ 同時 $g=O(f)$ 嗎？
有可能 $f=o(g)$ 同時 $g=o(f)$ 嗎？
如果 $f=O(2^n)$，$nf$ 也是 $O(2^n)$ 嗎？證明或給反例。
如果 $f=o(1)$，$nf$ 也是 $o(1)$ 嗎？證明或給反例。
考慮一個問題"判斷一個 $n$ 位數是否為完全平方數"。給一個多項式時間可以驗證的 certificate 來回答是。給一個多項式時間可以驗證的 certificate 來回答否。
Sign in with Wallet
Connect another wallet