---

5: 演算法複雜度 (2020/10/04~2020/10/10)

週五國慶日補假

---

這週要做的事

影片（每週二上課前完成）

• video 5: Big Oh and Little Oh
• reading assignment: 4.3 The Big "Oh" and Little "Oh" Notations
• questions 5

AL 分數 += Question 分數 * 0.01

HW5（下週二 5:00 pm 前交給助教）

請註明姓名學號以及第幾次作業

1. 證明對任意
   $ϵ>0$ 而言，
   $\ln (n)=o(n^{ϵ})$ 都成立。證明對任意
   $K>0$ 而言，
   $n^K=o(e^n)$ 都成立。
2. 證明
   
   $$(\genfrac{}{}{0ex}{}{2n}{n})={(\genfrac{}{}{0ex}{}{n}{0})}^2+{(\genfrac{}{}{0ex}{}{n}{1})}^2+\cdots +{(\genfrac{}{}{0ex}{}{n}{n})}^2$$

---

Big Oh and Little Oh

• Kahoot: Big Oh and Little Oh

若

$f:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$ 和

$g:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$ 為兩函數。

如果存在

$c>0$ 及

$n_0>0$ 使得

$f(n)\le cg(n)$ whenever

$n\ge n_0$，則我們說

$f=O(g)$（讀作

$f$ 是 "Big Oh of"

$g$）

如果

$$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=0$$
，則我們說

$f=o(g)$（讀作

$f$ 是 "Little oh of"

$g$）

---

用 Python 畫圖

Example on SageCell

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)$。

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$ 以下質數的個數。則

$$\underset{n\to \mathrm{\infty }}{lim}\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,\dots ,10000$ 中質數的個數是否大於
  $500$ 個。
• 判斷一個
  $n$ 位正整數是否可以被
  $m$ 位正整數整除 (
  $n\ge m$)。
• 判斷一個
  $n$ 位正整數是否為質數。
• 判斷
  $n$ 個數字中是否有一個子集其總合為
  $0$。

---

Summary: 證明組合等式

回顧一下這些等式的證明。

組合證明：

$$\sum _{k=1}^{n}2k-1=n^2$$

double counting：

$$(\genfrac{}{}{0ex}{}{n}{0})2^n+(\genfrac{}{}{0ex}{}{n}{1})2^{n-1}+\cdots +(\genfrac{}{}{0ex}{}{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,\dots ,100\}$ 中任取

$51$ 個數字，一定有其中兩個數字互質。

證明從

$\{1,\dots ,100\}$ 中任取

$51$ 個數字，一定有兩個數字總和為

$101$。

證明從

$\{1,\dots ,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 來回答否。