Introduction 基本概念 授課老師：蕭志明

Presentation on theme: "Introduction 基本概念 授課老師：蕭志明"— Presentation transcript:

1 Introduction 基本概念 授課老師：蕭志明

2 資料 基本資料：單一而不可以再分割的資料個體。 複合資料: 可被分解為多個有意義的基本資料。 例如，整數45 就是一個單一的整數數值。
程式中宣告： integer， char…. 複合資料: 可被分解為多個有意義的基本資料。 例如，以住址來說，可以被區隔為縣 ( 市 )、鄉 ( 鎮 )、道路等。

3 資料型態 資料的集合：整數、浮點數、字串 …。 運算的集合：資料型態各有其特殊的操作，像整數的加、減、乘、除運算。

4 資料結構 資料結構是由基本資料與複合資料所組成，而且可以定義資料之間的依存關係。 結構係指儲存資料的一組規則。
如果我們選取一組資料型態，並且將它們放入一個結構中並定義此結構的相關規則，那麼我們就是在製作一個資料結構。 許多個資料結構可以巢狀的方式結合在一起。 一個資料結構可以由其他資料結構所組成。

5 資料結構範例 陣 列 記 錄 由型態相同的資料所組成的循序串列 由型態不同的資料所組成的單一結構，並有一個識別鍵 組成元素間位置的相互關連
定義了兩個資料結構，陣列 (Array) 與記錄 (Record)。 陣　　列 記　　錄 由型態相同的資料所組成的循序串列 由型態不同的資料所組成的單一結構，並有一個識別鍵 組成元素間位置的相互關連 沒有關連 Ex： int Array[10] Record person { Char ID; String name; int phone; …. }

6 Example－用陣列 1. 資料的定義與組識 2. 和資料有關的操作 資料結構 排隊陣列的相關操作

7 資料型態(續) 基本資料型態：例如：整數、浮點數、字串、日期、布林值（Boolean value）等，都算是基本資料型態，這些資料型態各有其特殊的操作，像整數的加、減、乘、除運算，或是布林值的邏輯運算，從廣義的說，其實基本資料型態可以看成是最簡易的資料結構。 抽象資料型態 （ADT，Abstract data type）： 所謂的「抽象化」，在此是指將現實世界的事物或觀念轉化成資料結構來表示，ADT在設計上希望做到隱藏內部細節，展現平易外觀的目的，也就是讓使用者能善用ADT，卻不必了解其內部的詳細結構。

8 抽象資料型式（ADT Data Type） 圖中最底層的部分，這些基本型式的資料可結合成各種抽象資料型式

9 ADT　Example 1. 資料的定義與組識 2. 和資料有關的操作 資料結構 排隊陣列的相關操作

10 抽象資料型態（續） 在使用ADT的時候，我們並不在意ADT如何完成工作，而是它能夠做什麼樣的工作。
所謂抽象，就是未載明一般實作方式的運算。我們抽象化程序處理的本質，而將實作細節隱藏起來。

11 至少有三種資料結構可用來支援串列，例如陣列、連結串列、與檔案。
何謂抽象： 我們可以知道一個資料型態能作什麼工作； 資料型態如何完成工作則被隱藏起來。 抽象資料型態包括： 資料的宣告； 運算的宣告； 資料與運算的封裝。 至少有三種資料結構可用來支援串列，例如陣列、連結串列、與檔案。 如果我們將串列放在ADT中，ADT的使用者不應該知道我們使用的是那一種結構。使用者只要能夠對串列進行資料的插入與讀取即可。

12 抽象資料型態的模型

13 ADT的模型 呈現不規則狀且反白的區域代表整個模型。 在這個抽象的區域之內，是由模型的兩大部份，資料結構與運算函數所組成。
兩者都包含在區域之內，而且使用者無法存取它們。 但是其中的函數可以存取所有的資料結構，而且很可能會呼叫其他函數來完成工作。換句話說，區域內的資料結構與運算函數之間是沒有隔閡的。

14 ADT運算 圖中有一些長方格，只有一半在區域之內，是所謂的操作介面，資料可經由此進行輸入、讀取、更新、與刪除等處理的工作。
對於介面中的每一個操作都有一個對應的演算法來實作。長方格中所包含的內容就是操作的表頭。 由表頭可知使用者只能知道操作名稱與參數，而且這些操作是存取ADT的唯一介面。

15 ADT資料結構 ADT要對使用者隱藏實作細節 ，不過結構的所有資料都必須在ADT中維護。
也就因為要儲存不同的資料，所以必須對使用者隱藏實作的細節。 ADT類別所屬的物件都會有一個定義好的型態，而且使用者也必需要使用這些型態來撰寫程式。 當物件建立之後，它會包含所有需要的結構。應用程式不必關注這些結構確切的格式與型態。 就一個實務問題而言，我們會將這些結構實作在動態記憶體中。

16 一個指標(指向一個被穩藏的結構 )

17 演算法（Algorithms） 演算法(algorithm)： 由有限步驟所構成的集合，可以用於解決某一個特定的問題。
是一解決問題（problems）的有限步驟程序。 舉例來說，現有一問題為：判斷數字x是否在一已排序好的數字串列s中。 其演算法為：從s串列的第一個元素開始，依序的比較，直到x被發現或s串列已達盡頭。假使x被找到，則印出Yes；否則，印出No。

18 演算法（續） 當問題很複雜時，上述敘述性的演算法就難以表達出來。因此，演算法大都以類似的程式語言表達之，繼而利用您所熟悉的程式語言執行之。

19 演算法條件 演算法必須滿足以下五個條件： 輸入(input)：可以由外界輸入0個、1個或多個以上的資料。
輸出(output)：至少要有1個以上的輸出。 明確性(definiteness)：每個步驟都必須是明確而不含糊的。 有限性(finiteness)：必須在有限步驟內結束。 有效性(effectiveness)：每一個步驟必須是基本的(可行的)，也就是說，即使我們僅僅具有紙和筆也可以執行這些步驟。

20 資料結構和演算法 資料結構和演算法要用程式語言來描述，才能交由電腦執行，至於要用那一種程式語言；並沒有特別規定

21 演算法效率分析 影響程式執行時間的因素，最簡單的有 演算法(algorithm)是一解決問 題的有限步驟之程序。
機器的速度 演算法的好壞 演算法(algorithm)是一解決問 題的有限步驟之程序。 演算法的好壞，必須做複雜度 的分析(complexity analysis)。 分析演算法的複雜度，必須先 求出程式中每一敘述的執行次 數，並加總起來，然後求出其 Big-O。

22 演算法效率分析（續） 我們必須要知道如何計算演算法的效率，以便選擇效率高的來使用。
如果一個程式不包含迴圈，那麼它的效率就與指令的總數目相關(在數學上稱為函數關係)。 演算法如果包含迴圈，那麼它的效率的變動情形就會很大，所以迴圈是我們分析的重點所在。 研究一個演算法時，通常都以一個表示被處理資料數目的函數，來衡量所謂的效率。一般格式如下： f (n) = 效率

23 程式執行時間 例如： 執行時間 = 執行次數 * 每次執行所需的時間。
由於每一敘述所需的時間必須考慮到機器 和編譯器的功能，因此通常只考慮執行的 次數而已。 例如： x=x+1; for (i=1; i <= n; i++) for(i=1; i<=n; i++) x=x+1; for(j=1; j<=n; j++) x=x+1; 1次 n次 n2次

24 陣列元素相加 int sum(int arr[ ], int n) { int i, total=0;
for (i=0; i < n; i++) total += arr[i]; return total; } 執行次數 1 n+1 n ________ 2n+3

25 矩陣相加 假設兩矩陣a, b皆為n*n。 執行次數
void add(int a[ ][ ], int b[ ][ ], int c[ ][ ], int n) { int i, j; for(i=0; i<n; i++) for (j=0; j<n; j++) c[i][j] =a[i][j]+b[i][j]; } 執行次數 1 n+1 n(n+1) n2 ________ 2n2+2n+2

26 矩陣相加

27 矩陣相乘 執行次數 1 n+1 for (i=0; i < n; i++) n(n+1)
void mul(int a[ ][ ], int b[ ][ ], int c[ ][ ], int n) { int i, j, k, sum; for (i=0; i < n; i++) for (j=0; j < n; j++) sum = 0; for (k=0; k < n; k++) sum = sum+a[i][k]*b[k][j]; c[i][j] = sum; } 執行次數 1 n+1 n(n+1) n2 n2(n+1) n3 ___________ 2n3+4n2+2n+2

28 相乘兩個矩陣 矩陣相乘（Matrix Multiplication）

29 相乘兩個矩陣

30 Big-O 算完程式敘述的執行次數後，通常 利用Big-O來表示此演算法的執行 時間，表示如O(n)，亦稱為該程式 的「時間複雜度(time complexity)」。 Big-O取執行次數中最高次方或最 大指數部份的項目即可。 如： 陣列元素相加為2n+3 = O(n) 矩陣相加為2n2+2n+1 = O(n2) 矩陣相乘為2n3+4n2+2n+2 = O(n3) 運用時間複雜度的觀念，我們可以 判斷該程式的執行效率是否良好。 衡量程式效率的方法還有與。

31 Big-O　定義

32 Big-O 範例 請看下列範例： (a) 3n+2=O(n)，∵我們可找到c=4，n0=2,使得3n+2 < 4n
(b) 10n2+5n+1=O(n2)，∵我們可以找到c=11, n0=6使得10n2+5n+1 < 11n2 (c) 7*2n +n2+n=O(2n)，∵我們可以找到c=8, n0=4使得7*2n +n2 +n < 8*2n (d) 10n2+5n+1=O(n3)，原來10n2+5n+1 O(n2)，而n3又大於n2，理所當然10n2+5n+1=O(n3 )是沒問題的。

33 Big-O　公式 　f(n)=amnm +...+a1n+a0 時，f(n)=O(nm)

34 Big-O 例如有一程式的執行次數為n2+10n，則其Big-O為n2，表示此程式執行的時間最壞的情況下不會超過n2，因為
n2+10n≦2n2，當c=2，n≧10時

35 Big-O 等級 O(1)：常數時間(constant time) O(log n)：次線性時間(sub-linear)
O(n)：線性時間(linear) O(n log n) O(n2)：平方時間(quadratic) O(n3)：立方時間(cubic) O(2n)：指數時間(exponential) O(n!)：階乘時間(factorial) 如果n很大時 → 1< log n < n < n log n < n2 < n3 < 2n < n!

36 Big-O　之效率

37 Example 若ㄧ個程式執行時間是1000n^2+nlogn,求其big-O

38 複雜度分析 以循序搜尋為例： int search (int data[ ], int target, int n) { int i;
for (i=0; i < n; i++) if ( target == data[i]) return[i]; } 最佳次數：當資料在第一筆時，第一次就找 到。 最差次數：當資料不存在或資料在最後一筆時，需要N次。 平均次數： O(n) 通常比較最差次數。

39 二元搜尋— O(?) binsrch(int A[], int n, int x, int j) { lower = 1;
upper = n; while (lower <= upper) mid = (lower + upper) / 2; if (x > A[mid]) lower = mid + 1; else if (x < A[mid]) upper = mid – 1; else { j = mid; return; }

40 二元搜尋 　二元搜尋法乃是資料已經皆排序好，因此由中間（mid）開始比較，便可知欲搜尋的資料（key）落在mid的左邊還是右邊，再將左邊的中間拿出來與key相比，只是每次要調整每個段落的起始位址或最終位址。

41 二元搜尋

42 二元搜尋 搜尋的次數為log32+1=6，此處的log表示log2。資料量為128個時，其搜尋的次數為log128+1，因此當資料量為n時，其執行的次數為logn+1。

43 二元搜尋Big-O 二元搜尋比循序搜尋好得太多了，其執行敘率為O(logn) 。