iT邦幫忙

2021 iThome 鐵人賽

DAY 17
0
Software Development

C++ 三十天學習紀錄系列 第 17

【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,也就是說其所需要跑 https://chart.googleapis.com/chart?cht=tx&amp;chl=C1*n 次 (C1為ㄧ定值),而 recursive 則是算 exponential time,也就是他會跑 https://chart.googleapis.com/chart?cht=tx&amp;chl=C2*2%5En 次(C2為一定值)。因此,當 n 大到一定程度時, https://chart.googleapis.com/chart?cht=tx&amp;chl=C2*2%5En 會大於 https://chart.googleapis.com/chart?cht=tx&amp;chl=C1*n

Searching

Search 是一個非常常見的遞迴應用。

假設我們現在有一個陣列A以及一整數 p,我們想要知道 p 是否在於A,而且這個陣列 A 是沒有排序過的陣列,一個最直觀的方法就是 linear search,就是從A的第一項開始判斷,從頭開始一個一個的找,這個方法簡單明瞭,不過呢,有的時候可能會有點沒效率,如果今天我們這個陣列是已經排序好了,使用 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 可以讓我們的效率大幅提升,我們只需要跑 https://chart.googleapis.com/chart?cht=tx&amp;chl=log_2n 次!

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

以上就是今天的內容!


上一篇
【Day 16】Function - Practice 2
下一篇
【Day 18】Complexity & Graphs
系列文
C++ 三十天學習紀錄30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言