本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。

Presentation on theme: "本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。"— Presentation transcript:

1 本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。
請依出版社授權使用規範利用本教學資源，非經授權許可不得以影印、拷貝、列印等方法進行重製，亦不得改作、公開展示著作內容，亦請勿對第三人公開傳輸、散布。 戴顯權 著 / 資料結構 © 滄海圖書

2 Chapter 1 簡介 戴顯權 著 / 資料結構 © 滄海圖書

3 本章內容 1.1　資料結構+ 演算法= 程式 1.2　C 語言回顧 1.3　漸近式複雜度 戴顯權 著 / 資料結構 © 滄海圖書

4 資料結構+ 演算法= 程式 如何讓程式執行速度很快 ? 選擇一個好的演算法才是最具決定性的一個因素 必須使用一個高執行速度的電腦 ? 錯 !
戴顯權 著 / 資料結構 © 滄海圖書

5 更快的電腦 或 更好的演算法？ 演算法的改進成效超過硬體的改進成效！ 例如，從 2n 到 n3 戴顯權 著 / 資料結構 © 滄海圖書

6 快速排序法與直接插入排序法 戴顯權 著 / 資料結構 © 滄海圖書

7 資料結構＋演算法＝程式 當輸入資料量大於 1200 筆時，快速排序法在慢電腦 的執行速度比直接插入排序法在快電腦上還快 !
因此，選擇一個好的演算法是影響程式執行效率的 因素當中最具決定性的一個 但是，沒有好的資料結構不可能有好的演算法 光有好的演算法而沒有好的資料結構的配合，程式 快不起來 戴顯權 著 / 資料結構 © 滄海圖書

8 資料結構＋演算法＝程式 例如，求圖 1.1 中的兩條曲線的交點 使用兩個大矩陣 A(i, j)、B(i, j) 來表示
如果曲線一通過座標 (i, j)，則設定 A(i, j) = 1；否則 A(i, j) = 0 如果曲線二通過座標 (i, j)，則設定 B(i, j) = 1；否則 B(i, j) = 0 另一種表示方法：分別記錄兩條曲線的點之座標 每一條曲線各有 10 個點 戴顯權 著 / 資料結構 © 滄海圖書

9 資料結構＋演算法＝程式 兩種表示法都可以用來求出這兩條曲線的交點，但 是演算法會不同
第一種表示法的演算法只需要讀入所有的 A(i, j) 與 B(i, j)，然後檢查看看是那一個座標 (i, j) 使得 A(i, j) ＝B(i, j) ＝1 需要比較大的記憶體 一開始在決定那些 A(i, j) 與 B(i, j) 要設為 1 時需要大量的 計算 演算法簡單，執行速度卻不見得快 戴顯權 著 / 資料結構 © 滄海圖書

10 資料結構＋演算法＝程式 第二種表示法 ：掃瞄兩條曲線直到它們的大小關係 反過來為止 n 1200 1400 直接插入排序法 11 14.97
快速排序法 11.09 13.21 戴顯權 著 / 資料結構 © 滄海圖書

11 資料結構＋演算法＝程式 總而言之，資料結構直接牽動著演算法的設計 而演算法又直接影響著程式的執行速度
當 n = 1400 時，兩條曲線的大小關係反過來了 因此交點的位置介於 n = 1200 與 n = 1400 之間 計算出兩個線段，分別是由 (1200, 11) 與(1400, 14.97) 所 形成的線段以及由 (1200, 11.09) 與(1400, 13.21) 所形成的 線段，的交點位置 總而言之，資料結構直接牽動著演算法的設計 而演算法又直接影響著程式的執行速度 戴顯權 著 / 資料結構 © 滄海圖書

12 資料結構＋演算法＝程式 好的資料結構＋好的演算法＝好的程式 資料結構：表示資料的方法 演算法：處理資料的方法 程式：C
戴顯權 著 / 資料結構 © 滄海圖書

13 C 語言回顧 變數宣告 一個整數變數的宣告方式是： 其他類型變數的宣告與這個例子相仿 int iYears;
戴顯權 著 / 資料結構 © 滄海圖書

14 C 語言回顧 陣列 宣告方式： int iData[5]; iData 自動被宣告成一個指標，指向這個整數陣列的第一 個
戴顯權 著 / 資料結構 © 滄海圖書

15 C 語言回顧 指標變數 指標是用來記住資料在記憶體中的位置 指向不同資料類型的各種指標屬於不同的資料類型 一個指向整數資料的指標的宣告方式：
int* pAmount; 宣告了一個叫做 pAmount 的整數指標，但尚未告訴 C 語 言這個指標的內容應該為何 戴顯權 著 / 資料結構 © 滄海圖書

16 C 語言回顧 指標變數 int Amount = 3; int* pAmount = & Amount; /* pAmount ← Amount 在記憶體的位置 */ 在這個例子中，我們先用宣告一個整數變數， Amount；然後我們又宣告了一個指向Amount 的整數 指標，pAmount，同時將pAmount 的內容值設定為 &Amount (即，變數Amount 在記憶體裡的位置) 戴顯權 著 / 資料結構 © 滄海圖書

17 C 語言回顧 指標變數 戴顯權 著 / 資料結構 © 滄海圖書

18 C 語言回顧 指標變數 在圖1.3 中，左側的數字代表記憶體位址，中間的數 字代表記憶體的內容，右側的文字則代表變數名稱。 從這個圖可以知道，pAmount 的值確實為Amount 的 記憶體位址。 在這一個例子中， 如果讀取pAmount， 我們將得到 x00FA0； 如果讀取*pAmount，我們將得到3，其中* 稱為取值運算子(dereferencing operator)。 戴顯權 著 / 資料結構 © 滄海圖書

19 C 語言回顧 自定資料型態 宣告了一種新的資料類型，稱為 PData
typedef struct PData { char sName[30]; int iAge; } PersonData; /* 宣告PersonData 為新的資料型態*/ 宣告了一種新的資料類型，稱為 PData 每一份 PData 資料類型內，都包含有兩個欄位： sName[30]、iAge 戴顯權 著 / 資料結構 © 滄海圖書

20 例題一物件陣 PersonData Classmates[20] － 宣告 Classmates[20] 裡 的每一項元素都是 PersonData 型態的變數 戴顯權 著 / 資料結構 © 滄海圖書

21 例題二指標陣列 PersonData *pClassmates [20] － 宣告 pClassmates[20] 裡的每一項元素都是指向 PersonData 型態的指標 戴顯權 著 / 資料結構 © 滄海圖書

22 C 語言回顧 遞迴 副程式利用多層次呼叫的方式呼叫自己來處理資料 費氏數列的定義是： f (0) = 0 f (1) = 1
f (n) = f (n – 1) + f (n – 2) 戴顯權 著 / 資料結構 © 滄海圖書

23 C 語言回顧 遞迴 程式： int Fibonacci(int n) { if (n==0) return 0; /* f (0)=0*/
else if (n==1) return 1; /* f (1)=1*/ else /* f (n)= f (n–1)+ f (n–2)*/ return Fibonacci(n–1)+Fibonacci(n–2); } 戴顯權 著 / 資料結構 © 滄海圖書

24 漸近式複雜度 假設i, j, k, N 都宣告為整數變數：
for(i=1; i<N+1; i++) for( j=0; j<i; j++) k++; 時間複雜度可以表示為一個big-O 函數，即寫成 T(N) = O(N2)，這也就是所謂的漸近式複雜度(asymptotic complexity) 戴顯權 著 / 資料結構 © 滄海圖書

25 漸近式複雜度 f(n) = O(g(n)) 戴顯權 著 / 資料結構 © 滄海圖書

26 例題三 假設 f(n) = n2 + 2 且 g(n) = n2。
取 c = 4, n0 = 2，那麼當 n  n0 時，0  f(n)  cg(n) 必 定成立，因此我們說 f(n) = O(g(n)) = O(n2)。 戴顯權 著 / 資料結構 © 滄海圖書

27 例題四 假設 f(n) = n3 + n，那麼 f(n) = O(n3)。
戴顯權 著 / 資料結構 © 滄海圖書

28 漸近式複雜度 以上的不等式只假設當n 夠大的時候成立；它們是近 似的不等式
O 所提供給我們的是一個演算法的計算複雜度上限 (upper bound)； 所提供給我們的則是一個演算法的 計算複雜度下限(lower bound)；而  所提供給我們的 同時是一個演算法的計算複雜度上限與下限 戴顯權 著 / 資料結構 © 滄海圖書

29 漸近式複雜度 常見的演算法複雜度有： 戴顯權 著 / 資料結構 © 滄海圖書

30 漸近式複雜度 O(1) < O(loglogn) < O(logn) < O(n) < O(nlogn) < O(na) < O(2n)。 戴顯權 著 / 資料結構 © 滄海圖書

31 漸近式複雜度 戴顯權 著 / 資料結構 © 滄海圖書