簡介

這篇是演算大法的下半部。

有 sorting 、 search 各兩種方式以及他們的差別。

Complexity issue of recursion

有時候 recursion 跟 loop 是可以互換的，因為他們本質上都是迴圈一直跑一直跑

像是 finding maximum 跟 factorial 其實效率是差不多的

但是有時候會 A > B 或是 B > A

像是 Fibonacci sequence 的 recursion 效率就會比 iterative function 的效率來的差:

如果是用遞迴寫的話:

int fib(int n)
{
	if (n == 1) // stopping condition
		return 1;
	else if (n == 2) // stopping condition
		return 1;
	else
		// recursive call
		return (fib(n - 1) + fib (n -2));
}

如果是用 loop 直接寫的話:

double fibRepetitive(int a) // in loop
{
	if(n == 1 || n == 2)
		return 1;
	int fib1 = 0, fib2 = 0;
	int fib3 = 0;
	for (int i = 2; i < n; i ++)
	{
		fib3 = fib1 + fib 2;
		fib1 = fib2;
		fib2 = fib3;
	}
	return fib3;
}

如果把它圖像化的話，會長成這樣:

可以發現，用 Recursion 的方式的確是比較好懂一點。

但是，到底誰比較快呢 ?

我們拿這樣來比較:

int main()
{	int n = 0;
	cin >> n; 
	cout << fibRepetitive(n);
	cout << "\n";
	cout << fib(n);
	return 0;
}

雖然一開始 1- 40以前的數字跑的速度都差不多，但是 n 到了 45左右就會開始

發現 fibRepetitive 一下就跑出來了，但是 fub卻要等個1 - 2秒 左右

所以可以證明說 使用 Repetitive function 的時候會比較有效率

為什麼?

Polynomial time vs. exponential time

Repetitive : 只需要 c1 * n 個步驟(c1 is a constant)

Recursion: 則需要 c2 * 2^n個步驟 (c2 is a constant)

用圖來表示 Recursion 的話就會長這樣:

簡單說就是 recursion 的方式多跑了下面的那個 3 所以會比repetitive function 做了更多的事情，因此跑得會比較慢。

就算是 c1 >> c2 也沒辦法把 2^n給補回來。

在這邊

• 這個 repetitive 就會被稱為 polynomial algorithm: (也就是跟 n 成正比)
• 而這 recursion 則會被稱為 exponential-time algorithms (跟某數的 n 次方成正比)

所以一開始我們在想 algorithm 的時候，就必須先去除掉 exponential-time 的機會，因為當使用這種類型的 algorithm 的時候，程式的效率就會大大的減少

Power of recursion

雖然 recursion 的效率不優，但有些情況還是用 recursion 來做才更簡單。

有個例子: 何內塔 (Hanoi Tower)

• 目的: 我們要把 原本都在 pillar A 的盤子，全部移到 pillar C 上
  • 一次只能移動一個盤子
  • 小的盤子都可以放在大盤子上

像是這樣:

寫成程式:

#include<iostream>
using namespace std;

void hanoi(char from, char via, char to, int disc);

int main()
{
	int disc = 0; // number of discs
	cin >> disc;
	char a = 'A',  b = 'B', c = 'C';

	hanoi(a, b, c, disc);

	return 0;
}

void hanoi(char from, char via, char to, int disc)
{
	if (disc == 1)
		cout << "From " << from
			 << "to " << to << "\n";
	else
	{
		hanoi(from, to, via, disc - 1);
		cout << "From " << from
			 << "to " << to << "\n";
			 hanoi(via, from, to, disc - 1);
	}
}

簡單說 strategy 就是:

例如今天有四個 disc

我們就必須先把 (上面的 3 個disc 從 A 移到 B ) = subtask

所以程式跑出來會長成:

From A to B
From A to C
From B to C
From A to B
From C to A
From C to B
From A to B
From A to C
From B to C
From B to A
From C to A
From B to C
From A to B
From A to C
From B to C

如果自己想一遍會比較清楚:

影片

這樣子如果用 repetitive iterative 的做法，會更難懂。

Searching

從一群 element 中找到特定的一個 set

例如我們可以在 word 裡面按 ctrl + f 就可以打入你想要搜尋的資訊

練習的例子:

• 在一個一維陣列中 array (A[1....n])裡面尋找一個 integer (p)
  • 要怎麼知道 p 是不是存在 A?
  • 如果存在，那他在哪裡?

Linear Search:

如果陣列沒有排序是亂的→可以直接線性的尋找: 也就是一個一個找，需要做 n 次的判斷。

像是這樣 :

a[ ] = {5, 2 ,4, 3, 8, 9, 11}

如果要找 9 的話，就從 5, 2, ... 依序判斷，直到找到 9。

Binary Search:

1. 那如果陣列有排序過的話，就可以直接從 中位數 開始找:

   如果目標數字 = 中位數 → 那就是 他了

   如果目標數字 > 中位數 → 往上找 →再找中位數繼續做

   如果目標數字 < 中位數 → 往下找 →再找中位數繼續做

   例如:

   {2, 4, 5, 6, 7, 9, 11}

   中位數 6 < 8 所以 2, 4, 5 可以刪掉

   再看 7, 9, 11 中位數是 9 > 8 → 11刪掉

   最後剩下 7 ≠ 8 所以可以知道 8 不在裡面

   如果寫成 pseudocode:

   binarySearch(a sorted array A, search in between from and to, search for p)
   if n = 1
   	return true if A_from = p;
   	return false otherwise;
   else
   	let median be floor((from + to) / 2)
   	if p = A_median
   		return true
   	else if p < A_median
   		return binarySearch(A, from, median, p)
   	else
   		return binarySearch(A,median + 1, to, p)
   

   因此 binary search 會比 linear search 來的較有效率(在數字大的時候更能體現)，但是如果今天給你的是一個 unsorted 的陣列，這時候就不要再 sorting 了，因為 sorting 會更花時間?

Sorting

給予一個一維陣列 A，請排列。

Insertion sort:

例如今天給你 {6, 9, 3, 4, 7}

1. 首先把 6 拿出來 ， 右邊那一張是 9 > 6 所以 9 放在 6 的右邊

   {6 | 9, 3, 4, 7}

2. 接下來是 3 < 6，所以排 6 的左邊

   {3, 6, 9 | 4, 7}

3. 3 < 4 < 6，所以會插進 3, 6 的中間

   {3, 4, 6, 9 | 7}

4. 再做 7， 6 < 7 < 9，所以插到 6, 9 中間

   {3, 4, 6, 7, 9}

那要怎麼 implement ?

可以用看看 recursion

strategy:

1. 先把前 (n - 1) 數字排好
2. 再把 第n項 插進去

Pseudocode 寫起來:

insertionSort(a non-repetive array A, the array length n, an index cutoff < n)
// at any time, A_1~coutoff is sorted and A_(cutoff+1 ~ n) us unsorted
if A_cutoff+1 < A_1~coutoff
	let p be A[1]
else
	find p such that A_p-1 < A_cutoff+1 < A_p 
insert A_cutoff+1 to A_p and shift A_p~cutoff to A_p+1~coutoff+1
// 先存到 temp -> shift -> 再插入
if cutoff+1 < n
	insertionSort(A, n, cutoff + 1)

remark:

如果我們今天要把 kth 數字插入 左邊排序的數列

至多會有 k 的動作

所以可以粗估總共會有 1 + 2 + 3 + ... + n 個 operations(proportional to n^2) :

也就是說它是一個 polynomial-time algorithm

Mergesort: (Merge sort)

• 適用於處理數字非常多的時候
• 跟 insertion sort 的處理方式很像
• 但是當數字很多的時候，就會比 insertion sort 快很多

如果一次只插一個數字的話，又要先存取→平移→再插入，工程浩大

但如果一次插一串數字的話，感覺起來就比較不那麼麻煩了。

Strategy: Recursion

1. 先分一半，排左邊右邊
2. 再排兩個 subarray
3. 最後再 merge 兩個 subarrays

Pseudocode :

mergeSort(an array A, the array length n)
	let median be floor ((1 + n) / 2)
	mergeSort(A_1~median, median) // now A_1~median is sorted
	mergeSort(A_median+1~n, n - median + 1) // now A_median+1~n is sorted
	merge A_1~median and A_median+1~n // how????

要怎麼 merge?

可以舉一個例子:

{1, 3, 5, 7} & {2, 4, 6}

今天這兩個 array 要 merge，先創一個陣列 跟兩個陣列加起來總數一樣大

然後在1和2的頭上放上一個指標，

1 < 2 所以 1 放在第一個位置 A[0] ，接下來那個指標就丟給下一項 3

接下來 2 < 3，所以放到第二個位置A[1]，再把指標丟給下一項 4

繼續筆就會得到結果。

就有點像是蓋一個房子，如果你每一個東西都是一顆一顆螺絲鎖上去，釘上去，這樣在蓋房子的時候效率會減低很多；所以如果你先組裝好一些東西，再一次搬過去就會比較輕鬆。

心得

這次教的東西，我在youtube曾經有看過，覺得超酷的!

分享給大家：　

searching

sorting