简介

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

有 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