---
# System prepended metadata

title: 演算法作業01
tags: [algorithm, learning, neopolitan]

---

###### tags: `learning` `algorithm` `neopolitan`

# 演算法作業01

## ch1 習題 5 求最大公因數
用輾轉相除法，迭代版，以pseudocode
```python=
int gcd(int a, int b)
{                  // 不用判斷大小與交換，會自己換
    while (b != 0) // 處理b為零，或直到b為零
    {
        int remainder = a % b;
        (a, b) = (b, remainder); // 相當於遞迴
    }
    return a;
}
```
用輾轉相除法，遞迴版，用python實作
```python=
def gcd(a,b):  
    if (b == 0): 
         return a 
    return gcd(b, a%b) # 呼叫自己
```
## ch1 習題 6 找最大和最小
共有n個數，
先倆倆比大小，於是要比n/2次，被分成比較大的那一組和比較小的那一組。
然後兩組內再兩倆比大小，於是比了n/2次。
但這次大的組只留大的，小的組只留小的。
比完之後大的組和小的組的大小都只剩原來的一半。
一直比，直到大的組中只剩最大的，小的組中只剩最小的。
如果n取很大又是二的次方數，這樣共要比n/2+n/2(1+1/2+1/4+1/8+...)會逼近1.5n次。
```python=
def min_and_max(S):  # 把S分成大的組S_max和小的組S_min
    S_min = []
    S_max = []
    for i in range(len(S)//2):
        if S[i*2] >= S[i*2+1]:
            S_max.append(S[2*i])
            S_min.append(S[2*i+1])
        else:
            S_min.append(S[2*i])
            S_max.append(S[2*i+1])
    return S_min, S_max

def my_min(S): 
    if len(S) >1:
        S_min_min = []
        for i in list(range(len(S)//2)):
            if S[2*i] >= S[2*i+1]:
                S_min_min.append(S[2*i+1])
            else:
                S_min_min.append(S[2*i])
        return my_min(S_min_min)  # recursive
    else:
        return S

def my_max(S): 
    if len(S) >1:
        S_max_max = []
        for i in list(range(len(S)//2)):
            if S[2*i] >= S[2*i+1]:
                S_max_max.append(S[2*i])
            else:
                S_max_max.append(S[2*i+1])
                return my_max(S_max_max)  # recursive
    else:
        return S

S = [10, 20, 30, 40, 50, 60, 70, 80]
S_min, S_max = min_and_max(S)
print(S_min)
print(my_min(S_min))
print(S_max)
print(my_max(S_max))
```
## 15 證明 $n^2+3n^3\in\Theta(n^3)$
+ $f(n)=n^2+3n^3\in O(n^3)$
    + 對於所有 $n\geq1$，顯然有 $n^2+3n^3\leq n^3 + 3n^3=4n^3$ ，故得證。
+ $f(n)=n^2+3n^3\in\Omega(n^3)$
    + 對於所有 $n\geq1$，顯然有 $n^2+3n^3\geq n^3$ ，故得證。
    
綜上所述，$f(n)=n^2+3n^3\in\Theta(n^3)$。
## 18 證明 $p(n) \in \Theta(n^k)$
$p(n)=a_k n^k+a_{k-1} n^{k-1}+\dots+a_2 n^2+a_1 n^1+a_0$
+ 先證 $p(n) \in O(n^k)$
    + 因為不知道$a_k$以外的$a_{k-1},\ldots,a_{1},a_{0}$們的正負，
我沒辦法宣稱
\begin{aligned}
     a_k n^k&+a_{k-1} n^{k-1}     + \dots+a_2 n^2 +a_1 n^1  +a_0 \\
\leq a_k n^k&+a_{k-1} n^{k} \;\;\: + \dots+a_2 n^k +a_1 n^k  +a_0
\end{aligned}

  + 於是找出 $a_i \: (i=0,1,\dots,k)$ 中最大的$a_{max}$，我們就可以宣稱 $\forall n>1$
\begin{aligned}
a_k n^k&+a_{k-1} n^{k-1}     +\dots + \;\;\:a_2     n^2 + \;\;\:a_1     n  \;+ a_0 \\
\leq a_{max} n^k&+a_{max} n^{k} \;\;\: +\dots + a_{max} n^k + a_{max} n^k  + a_{max} n^k \\
=  (k+1)& a_{max} n^k
\end{aligned}
+ 再證 $p(n) \in \Omega(n^k)$
取 $a_k>c=a_k/2$ ，解
\begin{aligned}
     (a_k-c) n^k&+a_{k-1} n^{k-1}     + \dots+a_2 n^2 +a_1 n^1  +a_0 = 0
\end{aligned}
令最大的實數根為 $n_0$ (若沒有實數根則代表所有係數都是正的，則下方不等式顯然成立)，對於$n > n_0$
\begin{aligned}
     a_k n^k&+a_{k-1} n^{k-1}     + \dots+a_2 n^2 +a_1 n^1  +a_0 \geq c n^k
\end{aligned}

綜上所述，$p(n)=\Theta(n^k)$。
## 22 
- Θ(n ln n)
- Θ(lg n) < Θ((lg n)^2) < Θ(n)
    - 亞線性
- Θ( 5n^2+7n ) = Θ( n^2 ) 
    - 次方
- Θ(n^2) < Θ(n^(5/2)) < Θ(n^3) 
    - 次方
- Θ(n!) 
    - 階層
- Θ(2^n!^) > Θ(n!) 比指數還快
    - $n!≒n^{n+1/2}e^{-n}$
    - 因為$\frac{d}{dn}2^{n!}=e^{(\ln2)(n!)}\ln2\frac{d}{dn}(n!)$所以比$n!$還快
- Θ(4^n^) 
    - 指數
- Θ(n^n^)
    - 比階層快
- $Θ(n^n + \ln n) = Θ(n^n)$
    
- $Θ(5^{\lg n}) = Θ( n^{\lg 5})$ 指數
- $Θ(n!) = Θ(n\lg n + 0.5\lg n - n)=Θ(n\lg n)$
- $(\lg n)!≒(\lg n)^{\lg n+0.5} e^{-\lg n}≒n^{-1} \sqrt{\lg n}(\lg n)^{\lg n}=e^{-\lg n+0.5\lg\lg n+(\lg\lg n)\lg n}$
  - ~~不太確定，應該是跟指數一樣快~~
  - 比指數慢
- n^0.5^ 比線性慢
- e^n^ 指數
- 8n+12 一次線性
- 10^n^+n^20^ 指數

## 25 
時間複雜度除以效能等於耗時。

時間複雜度 / 效能 = 耗時


現在效能變1000倍。

(a) T(n)
- 改變前
  - 問題實例的大小 1000單位
    時間複雜度 1000單位
    時間複雜度1000單位 / 效能1000單位 = 1分鐘
- 改變後
  - 問題實例的大小 1000\*1000單位
    時間複雜度 1000\*1000單位
    時間複雜度1000\*1000單位 / 效能1000\*1000單位 = 1分鐘
    
(b) T(n^3)
- 改變前
  - 問題實例的大小 1000單位
    時間複雜度 1000^3單位 = 10^9單位
    時間複雜度10^9單位 / 效能10^9單位 = 1分鐘
- 改變後
  - 問題實例的大小 1000\*10單位
    時間複雜度 10^12單位
    時間複雜度10^12單位 / 效能10^9\*1000單位 = 1分鐘
    
(c\) T(10^n)
- 改變前
  - 問題實例的大小 1000單位
    時間複雜度 10^1000單位
    時間複雜度10^1000單位 / 效能10^1000單位 = 1分鐘
- 改變後
  - 問題實例的大小 1003單位
    時間複雜度 10^1003單位
    時間複雜度10*1003單位 / 效能10^1003單位 = 1分鐘
## 34
while-loop 裡面的主要block會執行k+(k-1)+...+2+1=k(k+1)/2次，
所以整個演算法是Θ(k^2^)，也就是Θ(log(n)^2)。
## 37 
在 lg(n) 的時間複雜度求 x^n^ % p，
假設 n = 2^k^
```python=
def pow_Theta_lg_n(x, k, p): 
    temp = x
    for _ in range(k):
        temp = ((temp % p) ** 2) % p
    return(temp)
    
x = 3234
p = 1177
k = 1007

exam = pow_Theta_lg_n(x, k, p) - pow(x, 2**k, p)
print(exam)
```