[Algorithm] Day.2 演算法基本介紹 Part.2

2023-03-10

#algorithm #note

昨天介紹了什麼是演算法、虛擬碼跟遞迴演算法，最後還詳細的跑了一次河內塔。今天就讓我們繼續演算法的基本介紹吧！

1.3 Performance Analysis 效能分析

學習演算法的主要目的除了把問題解決以外，還要漂亮的把問題解決，也就是要有好的效能！那要怎麼量測一個演算法的效能呢，我們可以分成 空間複雜度 以及 時間複雜度 兩個指標

1.3.1 Space Complexity 空間複雜度

空間複雜度就是一個演算法所需要的記憶體空間

我們可以把空間複雜度分為 Fixed part 和 Variable part 兩個部分，其中 Fixed part 就包含了程式碼本身、常數和一些範例的變數；而 Variable part 則是會隨著程式的運作而改變的部分，通常會包含變數以及遞迴堆疊的空間。

1.3.2 Time Complexity 時間複雜度

時間複雜度就是執行一個演算法所需要的時間，通常用 CPU Time 作為單位

然而雖然說是執行演算法所需要的時間，但因為要準確的測量 CPU Time 以及到底一個指令要多少時間跑是非常困難的事情，所以準確的說時間複雜度指的是演算法的當中的 statement 被執行了多少次

用最原始的方式算的話其實也蠻簡單的，只需要在原本的程式中適當的加入一些計算執行次數的程式，我們可以像下面這個例子：

Algorithm Sum(a,n) {
	s = 0.0;
	count = count + 1 //count 為一個初始值為 0 的全域變數，用來計算執行次數
	for i = 1 to n do {
		count = count + 1 //每一圈 for 的判斷都 +1
		s = s + a[i];
		count = count + 1 //重新賦值 s 所以 +1
	}
	count = count + 1 //最後一圈 for
	count = count + 1 //return 的指令
	return s;
}

雖然說在一個簡單的演算法當中加入計數的程式看起來沒有很難，但想像當演算法變得更複雜之後，這個加入計數的過程勢必會變得更加困難！所以我們就會需要一個更簡單一點的表示方法 — Big-O

1.3.2.1 Big-O notation

Big-O 的在維基百科的定義就是用另一個（通常更簡單的）函式 (g(n)) 來描述一個函式 (f(n)) 數量級的漸近上界。

意思就是他是用來計算某一個演算法的天花板的，在時間複雜度裡面就是在計算一個演算法最多所需要花的時間。我們常見的 Big-O notation 有 O(1) 、 O(log n) 、 O(n) 、 O(n log n) 、 O(n^2) 、 O(2^n) 等。另外這個描述函式數量級的函式 (g(n)) 必須要越小越好，因為這個上界必須要越嚴謹越好

1.3.2.2 Big-Ω notation

這個和 Big-O notation 很像，但他表示的是 f(n) 的漸進下界，換成時間複雜度就是一個演算法所需要執行的最小時間

1.3.2.3 Big-Θ notation

這是當 Big-O 和 Big-Ω 相同的時候我們稱它為 Big-Θ，是一個理想的狀態

這三種 notation 都有一個特性，就是因為在執行次數越大的時候，較小次方的數值對整個演算法的影響會越來越小，因此 他們 只看 f(n) 的最高次方

另外因為工程師需要提升的是一個演算法最慢的執行速度，所以通常我們只在乎 Big-O，另外兩項比較是數學家在乎的領域了 XD

1.3.2.4 常見的 Big-O

big-o-complexity

說到 Big-O 我想大家都對這張圖不陌生，這些演算法的時間複雜度由小到大分別為

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)

那就來讓我們幫常見的演算法這些一個一個舉例吧：

  1. O(1)

    只要是沒有循環等複雜結構那麼這個程式碼的時間複雜度都是 O(1)，例如

    	Algorithm Oone () {
		i = 0;
		i ++;
		return i;
	}

  2. O(log n)

    Algorithm Ologn () {
	i = 1
	while i < n do {
		i = i * 10
	}
}

    在這個 while 迴圈裡面每次都將 i * 10，所以 i 會以對數的速度接近 n，我以我們稱之為 O(log n)，著名的 O(log n) 演算法就是 Binary search

  3. O(n)

    Algorithm On () {
	for i < n do {
		i = i + 1
	}
}

    在這個 for 迴圈裡面 i 是線性增加的，所以稱之為 O(n)，例子是 Linear search

  4. O(n log n)

    Algorithm Onlogn () {
	for i < n do {
		i = i + 1
		while j < n do {
			j = j * 10
		}
	}
}

    這裡的雙層迴圈裡面就是把 O(log n) 重複執行 n 次所以複雜度為 O(n log n)，例子是 Merge search

  5. O(n^2)

    Algorithm Onlogn () {
	for i < n do {
		i = i + 1
		for j < n do {
			j = j + 1
		}
	}
}

    這裡的雙層迴圈裡面就是把 O(n) 重複執行 n 次所以複雜度為 O(n*n) 也就是 O(n^2)，例子是 Bubble search

  6. O(2^n)

    根據教授上課時說話，這已經不能算是一個演算法，因為執行時間會隨著 n 變大而指數增加，對於演算法來說過度沒有效率

這樣我們基本上就介紹完了要如何測量一個演算法的效能，最後提一點就是因為最近的科技發達，所以記憶體基本上成本很低，所以在設計演算法的時候，通常是以時間複雜度為優先，就算犧牲一點空間複雜度也是非常可以接受的哦！

參考資料：

上一篇：
[Algorithm] Day.1 演算法基本介紹 Part.1下一篇：
[Algorithm] Day.3 隨機演算法