###### 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) ```