pedestrianlove/algorithm_examples

1. 估計執行時間

a. Notations

$$ \Theta(g(n)) = \{ f | \exists c_1, c_2, n_0 \Rightarrow 0 \leq c_1g(n) \leq f(n) \leq c_2g(n), \forall n\geq n_0 \} \\ $$

$$ O(g(n)) = \{ f | \exists c, n_0 \Rightarrow 0 \leq f(n) \leq cg(n), \forall n \geq n_0 \} \\ $$

$$ \Omega(g(n)) = \{ f | \exists c, n_0 \Rightarrow 0 \leq cg(n) \leq f(n), \forall n \geq n_0 \} $$

• Misc.

$$ lg(n!) = \Theta(nlgn) $$

b. Recursion

i. Substitution method (代入法)

• 猜解
• 代入用數學歸納法求證。

ii. Recursion tree method (畫遞迴樹)

• 列出每層遞迴的成本，並依樹的高度來估計時間複雜度。

iii. Master Theorem

比 $n^{\log_b(a)}$ 跟 $\log_n(f(n))$ 的大小(使用時間複雜度看):

• Case 1. $n^{\log_b(a)}$ 大，則 $T(n) = \Theta(n^{\log_b(a)})$
• Case 2. 平手，則 $T(n) = \Theta(n^{\log_b(a)}\log(n)) $
• Case 3. $\log_n(f(n))$ 大，且 $af(\frac{n}{b}) = c(f(n)), c<1, n\geq n_0$ ，則 $T(n)=\Theta(f(n))$

2. Sorting Algorithms

• 使用比較大小的排序終究無法逃脫決策樹模型的掌控，也就是 $\Omega(nlogn)$ 的限制。

a. Merge Sort

Algorithm_Examples/src/Sorting/MergeSort.ts

Lines 3 to 42 in 214cf53

	export class MergeSort implements SortingInterface {
	Merge(A: Array<number>, l: number, middle: number, r: number) {
	const L = A.slice(l, middle + 1);
	const R = A.slice(middle + 1, r+1);
	// Merge array
	let [i, j, k] = [0, 0, l];
	while (i < L.length && j < R.length) {
	if (L[i] <= R[j]) {
	A[k++] = L[i++];
	} else {
	A[k++] = R[j++];
	}
	}
	while (i < L.length) {
	A[k++] = L[i++];
	}
	while (j < R.length) {
	A[k++] = R[j++];
	}
	}
	MergeSort(A: Array<number>, l: number, r: number): void {
	if (l >= r) {
	return;
	}
	const middle = Math.floor((l + r) / 2);
	this.MergeSort(A, l, middle);
	this.MergeSort(A, middle + 1, r);
	this.Merge(A, l, middle, r);
	}
	Sort(A: Array<number>): Array<number> {
	this.MergeSort(A, 0, A.length-1);
	return A;
	}
	}

b. Heap Sort

Algorithm_Examples/src/Sorting/HeapSort.ts

Lines 3 to 54 in 214cf53

	export class HeapSort implements SortingInterface {
	heap_size = 0;
	static swap (x: number, y: number) {
	return [y, x];
	}
	Max_Heapify(A: Array<number>, i: number) {
	const [l, r] = [2*i, 2*i + 1];
	let largest = (l < this.heap_size && A[l] > A[i])
	? l
	: i;
	largest = (r < this.heap_size && A[r] > A[largest])
	? r
	: largest;
	if (largest != i) {
	[A[i], A[largest]] = HeapSort.swap(A[i], A[largest]);
	this.Max_Heapify(A, largest);
	}
	}
	Build_Max_Heap(A: Array<number>, n: number) {
	this.heap_size = n;
	for(let i = Math.floor(n/2) ; i >= 0; i--) {
	this.Max_Heapify(A, i);
	}
	}
	HeapSort (A: Array<number>, n: number) {
	this.Build_Max_Heap(A, n);
	this.heap_size = n;
	for (let i = n-1 ; i >= 1 ; i--) {
	[A[0], A[i]] = HeapSort.swap(A[0], A[i]);
	this.heap_size--;
	this.Max_Heapify(A, 0);
	}
	}
	Sort (A: Array<number>): Array<number> {
	this.HeapSort(A, A.length);
	return A;
	}
	}

c. Quick Sort

Algorithm_Examples/src/Sorting/QuickSort.ts

Lines 3 to 36 in 214cf53

	export class QuickSort implements SortingInterface {
	static swap (x: number, y: number): Array<number> {
	return [y, x];
	}
	Partition (A: Array<number>, p: number, r: number): number {
	const x = A[r];
	let i = p - 1;
	for (let j = p; j <= r-1 ; j++) {
	if (A[j] <= x) {
	i++;
	[A[i], A[j]] = QuickSort.swap(A[i], A[j]);
	}
	}
	[A[i+1], A[r]] = QuickSort.swap(A[i+1], A[r]);
	return i+1;
	}
	QuickSort (A: Array<number>, p: number, r: number) {
	if (p < r) {
	const q = this.Partition(A, p, r);
	this.QuickSort(A, p, q-1);
	this.QuickSort(A, q+1, r);
	}
	}
	Sort (A: Array<number>): Array<number> {
	this.QuickSort(A, 0, A.length - 1);
	return A;
	}
	}

d. Counting Sort

e. Radix Sort

f. Bucket Sort

3. Medians and order statistics

4. Binary Search Tree

• 左小右大

• 插入