【Day 17】Algorithm & Recursion 演算法 & 递回

有句话是 「programming = data structures + algorithms」，一个好的程序码需要好的资料结构与演算法，而演算法最看重的就是复杂度，复杂度越小，程序码就越有效率。

Algorithm

简而言之，演算法是用来解决问题的，而最常见的做法就是将一个大问题分解成好多个小问题，并解决这些子问题，而这样的方式称作递回 (recursion)。

此外，演算法中强调了两种复杂度，分别为空间复杂度(space complexity)与时间复杂度(time complexity)，在大部分的情况，时间复杂度比空间复杂度来得更重要。

Recursion

我们最常见的递回做法就是写一个函数并不断重复使用。
在河内塔(Hanoi tower)的例子中，应用递回是一个非常 clever 的做法，不过，并不是万灵丹，相信大家对Fibonacci数列都不陌生，就是 1, 1, 2, 3, 5, 8, 13, 21,...，从第三个数开始，每一项都是前两项的和，我们可以分别比较 recursion、repetitive 的做法：

Recursion

fib(n-1) + fib(n-2)

Repetitive

int fib1 = 1, fib2 = 1;
for (int i = 2; i < n; i++) {
	fib3 = fib1 + fib2
	fib1 = fib2	
	fib2 = fib3
}

在这样的情况下，选择 repetitive 的做法会比 recursion 来得更好，因为 repetitive 会花费的时间是 polynomial time，也就是说其所需要跑 次 （C1为ㄧ定值），而 recursive 则是算 exponential time，也就是他会跑 次（C2为一定值）。因此，当 n 大到一定程度时， 会大於 。

Searching

Search 是一个非常常见的递回应用。

假设我们现在有一个阵列Ａ以及一整数 p，我们想要知道 p 是否在於Ａ，而且这个阵列 A 是没有排序过的阵列，一个最直观的方法就是 linear search，就是从Ａ的第一项开始判断，从头开始一个一个的找，这个方法简单明了，不过呢，有的时候可能会有点没效率，如果今天我们这个阵列是已经排序好了，使用 binary search 可能更好。

Binary search
首先，我们先跟中位数 m 做比较，这时候我们有三种情况：

1. p = m：Bingo！
2. p < m：这时候我们知道如果 p 存在，就一定会在这个阵列的前半部。
3. p > m：这时候我们知道如果 p 存在，就一定会在这个阵列的後半部。

接着我们可以写一个函数

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

Binary search 可以让我们的效率大幅提升，我们只需要跑 次！

Sorting

有两种sorting的方式：insertion sort & merge sort。

Insertion sort

insertionSort(a non-repetitive array A, the array length n, an index cutoff < n)
// at any time, A1..cutoff is sorted and A(cutoff + 1)..n is unsorted

	if Acutoff + 1 < A1..cutoff
		let p be 1
	else
		find p such that Ap – 1 < Acutoff + 1 < Ap
		insert Acutoff + 1 to Ap
		and shift Ap..cutoff to A(p + 1)..(cutoff + 1)

	if cutoff + 1 < n
		insertionSort(A, n, cutoff + 1)

Merge sort

Merge sort 就是将一个排列好的阵列插入另一个排列好的阵列。

首先要先开一个跟总数一样大的阵列，接下来：

mergeSort(an array A, the array length n)
	let median be floor((1 + n) / 2)
	mergeSort(A1..median, median) 
	// now A1..median is sorted
	mergeSort(A(median + 1)..n, n – median + 1) 
	// now A(median + 1)..n is sorted

	merge A1..median and A(median + 1)..n

以上就是今天的内容！