# Ch1 Basic

# 基礎必會

• 背 2 的冪次方

• 能用 assignment、if-else 和 while 寫的演算法 (非遞迴解)，遞迴同樣能實現。

• 遞迴 & 非遞迴 比較表 (p1)

$$\begin{aligned} &\begin{array}{} \hline \text {項目} & \text {} & \text {遞迴} & \text {} & \text {非遞迴} \\ \hline & 優 & & 缺 & \\ 程式碼 && 精簡 && 冗長 \\ local和reg變數 && 使用少 && 使用很多 \\ 表達問題能力 && 好 && 差 \\ & 缺 & & 優 & \\ Debug && 困難 && 簡單 \\ 效率 && 較低 && 較高 \\ 額外空間需求 && stack && 無 \\ \hline \end{array} \end{aligned}$$

• Ackermann Function
  
  雖然題目會給公式，但是以下常考可以背起來:
  • A(1,2) = 4
  • A(2,1) = 5
  • A(2,2) = 7
  • A(2,3) = 9

以下基本演算法請記得它的遞迴定義

• Fibonacci number in O(n) by DP (p4)

  	int fac(int n) {
  	int f[n] = {0}; // 含 f [0] = 0
  	f[1] = 1;
  	if(n == 0) return f[0];
  	else if(n == 1) return f[1];
  	else {
  	for(int i = 2; i <= n; i++)
  	f[i] = f[i-1] + f[i-2];
  	}
  	return f[n];
  	}

• Binomial coefficient in O(n*k) by DP (p6)

  • 公式: $\binom{i}{j} = \binom{i-1}{j} + \binom{i-1}{j-1}$
  • code (use buttom up)

    	int binomialCoeff(int n, int k) {
    	int C[n+1][k+1];
    	for(int i = 0;i <= n; i++) {
    	for(int j = 0; j <= min(i, k); j++) {
    	//Base case
    	if(j == 0 || j == i)
    	C[i][j] = 1;
    	else
    	C[i][j] = C[i-1][j] + C[i-1][j-1];
    	}
    	}
    	return C[n][k];
    	}

  • Time complexity = space complexity = O(n*k)

• Greatest common divisor (GCD, 最大公因數): 使用 輾轉相除法

  • 公式: $\text{GCD}(a, b) = \begin{cases} b & \text{, if } a \mod b = 0 \\ \text{GCD}(b, a \mod b) & \text{, otherwise} \end{cases}$

• Recursive function for exponential xⁿ (p8)

  • 法一: time complexity O (n)
    • 公式: $x^n = \{ \begin{smallmatrix}1 & if n = 0 \\ x \cdot x^{n-1} & if n > 0 \end{smallmatrix}$
    • code:

      	int exp(int x, int n) {
      	if(n == 0) return 1;
      	else return x * exp(x, n-1);
      	}

  • 法二: time complexity O ($\log_2 n$)
    • 公式: $x^n = \{ \begin{smallmatrix}1 \cdot (x^2)^{\frac{n}{2}} & if n = even \\ x \cdot (x^2)^{\frac{n}{2}} & if n = odd \end{smallmatrix}$
    • code:

      	int exp(int x, int n) {
      	int f;
      	if((n%2) == 0) f = 1;
      	else f = x;
      	if(n < 2) return f;
      	else return f * exp(x*x, n/2);
      	}

• Tower of Hanoi 的遞迴解法 (印出每一步) (p9)

  • T(n) = 2ⁿ - 1

  	void towerOfHanoi(int n, char from, char to, char aux) { //aux 為中繼點
  	if(n == 1) {
  	printf("\n Move disk 1 from rod %c to rod %c", from, to);
  	return;
  	}
  	towerOfHanoi(n-1, from, aux, to); // 1. (n-1) 個從 source to aux
  	printf("\n Move disk %d from rod %c to rod %c", n, from, to); // 2. 第 n 個從 source to destination
  	towerOfHanoi(n-1, aux, to, from); // 3. (n-1) 個從 aux to destination
  	}

• 印出集合內所有 n 個元素的排列組合

  • 想法：每個元素輪流當頭，再遞迴呼叫小時候的結果
  • code:

    	char list[1..n];
    	void perm(char *list, int i, int n) {
    	if(i == n) { // 遞迴終止，印出當時 list 的答案
    	for(int j = 1; j <= n; j++) printf("%c", list[j]);
    	printf("\n");
    	} else { // i < n
    	for(int j = i; j <= n; j++) {
    	swap(list[i], list[j]); //list [j] 當頭
    	perm(list, i+1, n); // 印後面 i+1 ~ n 的排列
    	swap(list[i], list[j]); // 還原成原本 list 的內容
    	}
    	}
    	}
    	/* in main:
    	* char list[] = {'z', 'a', 'b', 'c', 'd'};
    	* perm(list, 1, 4);
    	*/

  • Time complexity = O(n*(n!))

• 用遞迴寫一個把字串反過來印的 function (不能用任何字串處理的函數) (p11)

  	void reverse(char *str) { // 傳入字元陣列的起始位址
  	if(*str) { // 非結束字元
  	reverse(str+1);
  	printf("%c", *str);
  	}
  	}

  	void reverse(char *str, int i, int j) {
  	if(i < j) {
  	// swap(str[i], str[j])
  	char temp = str[i];
  	str[i] = str[j];
  	str[j] = temp;
  	reverse(str, i+1, j-1);
  	}
  	}

• 基礎數學整理 (p14~19)

  1. $\sum_{i=1}^n i^d$, d >= 0, ≒ $n^{d+1}$
  2. 任何類似於 $\sum_{i=1}^k 2^i \cdot (k-i)$ 者，皆令 = S，並用 2S-S 展開
  3. 調和級數 $\sum_{i=1}^n \frac{1}{i} \in$ $\theta(\log n)$
  4. 階乘 (factorial)
     • n! ≤ nⁿ
     • n! ≒ $n^{n + \frac{1}{2}} \cdot e^{-n}$ ( Stirling's formula 的近似)
     • lg(n!) = $\theta(n \log n)$
  5. iterated logarithm function
     • 定義 lg*n = x 表對 n 取 x 次 $log_{2}$ 會變成 1
     • 推得 log*(logn) = (lg*n)-1

# 時間複雜度考題

1. Code/algorithm 指令執行次數
2. O, o, Ω, ω, θ 定義，性質，growth rate 大小比較
3. 解遞迴式，導出時間複雜度
   • 展開帶入
   • Master theory
   • Recursive tree
   • 特徵方程式
   • 猜近似值

進度: ppt p23
* 建議參考這篇 OS 的編排方式

Tools:

• 線上 Latex 編輯器
• latex 語法查詢