CS50 Week 3

Lecture

講解排序，分別有Bubble sort, Selection sort, 和Insertion sort

看看聲音搭配排序法的影片

Lecture, continued

講解排序的O(n)的意思，以及位元運算AND, OR, XOR, Shift。

Section

GDB

GDB是一個debugger，可以更清楚地了解程式錯誤訊息是甚麼，

是透過下commad line的方式debug，可以下中斷點，逐步去偵錯。

在cs50的IDE中，可以直接下gdb filename，就可進入debug模式。

Computational Complexity

計算的複雜度，從最簡單到最複雜如下:

Computational Complexity
O(1)	constant time
O(log n)	logarithmic time
O(n)	linear time
O(n lon n)	linearithmic time
O(n^2)	quadratic time
O(n^c)	polynomial time
O(c^n)	exponential time
O(n!)	factorial time
O(infinite)	infinite time

O(1)的例子如下:

int four_for_you(int array[1000]) {

     return 4;

}

O(n)的例子如下:

最差的情況下，要搜尋數字5，必須執行5次

2

4

1

3

5

最差的情況下，要搜尋數字5，必須執行7次

2

4

1

3

7

6

5

Selection Sort

在未排序的排列中，尋找最小的數值，並把它移到第一位；
舉例如下:
紅色為未排列

2

4

1

3

5

找到最小值 1

2

4

1

3

5

移到最前面，藍色為已排列，依此類推。

1

4

2

3

5

演算法複雜度如下:

• 最好的情況下: $\Omega (n^2)$
• 最壞的情況下:$O(n^2)$

Bubble Sort

在未排序的排列中，從最左邊兩個數值value[0], value[1]開始比較，

若value[0]比value[1]的大，則做交換位置，

重複步驟直到最右邊的兩個數值value[n-1], value[n]，

之後再回到value[1], value[2]比較，依此類推。

演算法複雜度如下:

• 最好的情況下: $\Omega (n)$
• 最壞的情況下:$O(n^2)$

Insertion Sort

假設value[0]是已排序的，檢查value[1]是否比value[0]小

若是的話，就把value[1]移到最左邊，之後檢查value[2]是否比

value[0]或value[1]小，依此類推。

演算法複雜度如下:

• 最好的情況下: $\Omega (n)$
• 最壞的情況下:$O(n^2)$

Merge Sort

2	4	1	3	6	5	未排序的陣列
2	4	1	3	6	5	切一半，分左半跟右半
2	4	1	3	6	5	左半再切一半，右半也再切一半
2	1	4	3	5	6	最左半只有2，所以暫時為已排序，左半的右半比較之後，4比1大，交換排序 後，也暫訂為已排序。右半依此類推。
1	2	4	3	5	6	左半的兩個部分做比較，2比1大做交換，2比4小，不做交換。 右半依此類推。
1	2	3	4	5	6	最後左半跟右半做比較，1跟2都比3小，不做交換，4比3大，做交換 。剩餘都不變，完成全部排序。

演算法複雜度如下:

• 最好的情況下: $\Omega (n log n)$
• 最壞的情況下:$O(n log n)$

因此，可以說明Merge Sort比其他基本排序還好，適合大量的資料應用。

Linear Search

在一個陣列中(n個數值)裡，逐步搜尋目標數值x。

因此，演算法複雜度如下:

• 最好的情況下: $\Omega (1)$
• 最壞的情況下:$O(n)$

Binary Search

在一個已經排序好的陣列數值裡，搜尋目標數值x。

舉例:

5	8	15	21	30	44	48
[0]	[1]	[2]	[3]	[4]	[5]	[6]

目標值: 15

起始值: 5 (陣列[0]) 終點值: 48 (陣列[6]) 中間值: 21 (陣列[(0+6)/2])

中間值21不等於目標值15，但我們知道15比21小，所以陣列減一半，

5	8	15
[0]	[1]	[2]

起始值: 5 (陣列[0]) 終點值: 15 (陣列[2]) 中間值: 8 (陣列[(0+2)/2])

中間值8不等於目標值15，但我們知道15比8大，所以陣列再減一半，

15

[2]

起始值: 15 (陣列[2]) 終點值: 15 (陣列[2]) 中間值: 15 (陣列[(2+2)/2])

中間值15等於目標值15，結束這回合XD。

因此，演算法複雜度如下:

• 最好的情況下: $\Omega (1)$
• 最壞的情況下:$O(log n)$

Shorts

Asymptotic Notation

講述Asymptotic complexity的Big O是log n，相較其他的n或是$n^2$都要

好，在輸入資料很大的時候。下圖可以看出log n的優點(X軸是資料量，Y

軸是時間)。

之後講得有點重複(Binary search, Bubble sort, Insertion sort, Linear search, Quick sort, Selection sort)，所以我就跳過沒看了XD。

然後，我的重點不是在於完整地完成這個CS50課程，而是想要快速地了解

HTML, CSS, 機器學習等，因此，Problem set我就不會再做了。