《一章节基本概念.ppt》由会员分享,可在线阅读,更多相关《一章节基本概念.ppt(29页珍藏版)》请在三一文库上搜索。
1、資料結構與演算法 徐熊健,1-1,第一章 基本概念,資料結構與演算法,徐熊健,資料結構與演算法 徐熊健,1-2,目錄,1.1 資料結構、演算法 1.2 資料結構與演算法 1.3 簡單的資料結構 1.4 演算法初探 1.5 演算法的效率分析,資料結構與演算法 徐熊健,1-3,1.1 資料結構、演算法,資料結構(data structure): 在電腦中有效率地存放資料,使其方便處理的學問; 演算法(algorithm): 探討解決問題的策略。 兩者相輔相成!,資料結構與演算法 徐熊健,1-4,1.2 資料結構與演算法,電腦處理的對象稱為資料(data),泛指所有輸入至電腦中,即將、正在或已經被電
2、腦程式處理的符號總稱;包括了數值(numerical) 資料、字串 (string) 資料等等,乃至於目前多媒體 (multimedia) 軟體所處理的影像、聲音、視訊等多媒體資料。 當這些資料集合在一起時,會因處理需求的不同而存在一種或多種彼此之間的特定關係,這些資料之間的邏輯關係,就稱為結構 (structure)。研究資料的邏輯關係,探討這些邏輯關係在電腦中的表現 (representation) 和處理 (manipulation) 方式,即為資料結構。,資料結構與演算法 徐熊健,1-5,1.3 簡單的資料結構,生活中常見的資料相互關係: (1)校園中有一群人; (2)每個中華民國國民
3、皆有唯一的身分證字號; (3) 每位同學在班上皆有唯一的座號、在學校皆有唯一的學號; (4)在大學中的科系有系別、年級別、甚至於班別; (5) 排隊的時候,我們可能只關心排在前一位的是誰?有時可能還在意排在自己前面的共有多少人? (6)外國旅行時,各景點間是否有班機直飛? (7)上網尋找資料,網頁間的鏈結,將網頁連結成複雜的全球性的網絡(world-wide web)。,資料結構與演算法 徐熊健,1-6,1.4 演算法初探,Horowitz, Sahni 和 Mehta ,給予演算法的明確定義: 演算法是一組可完成特定工作的指令集合,並且所有的演算法都需滿足下列條件: (1) 輸入 (inpu
4、t):可以有多個其甚至是沒有輸入; (2) 輸出 (output):至少產生一個輸出; (3) 明確(definiteness):每個指令都清楚明確; (4) 有限(finiteness):在任何情況下,如果逐步追蹤演算 法的每個指令,演算法會在有限的步驟內結束; (5) 有效率 (effectiveness):原則上每個指令都需 基本到 人只需紙和筆即可實踐之,並且每個指令的運算 不止如條件(3)般明確而已,還必須是可實行的。,資料結構與演算法 徐熊健,1-7,1.4.1程式撰寫流程,撰寫程式解決問題流程圖,資料結構與演算法 徐熊健,1-8,範例1-2 挑選排序法,思考與探索: 欲將整數由小
5、至大排序,可把數字小者放在左邊,數字小者放在右邊, 可以挑出所有資料中最小者,做為左邊第一筆資料,接著再挑出剩下資料中最小者,放在左邊做為第二筆資料,依此類推,直至全部資料都排列完成。 若所有資料共計n筆,則會執行n次挑出最小的運算,其第 i 次的運算,即為挑出未排序資料中最小者,其結果做為第i筆資料。,資料結構與演算法 徐熊健,1-9,演算法1-1 挑選排序法:,輸入:data0, data1, data2, , datan-1,共 n 筆整數資料 輸出:data0, data1, datan-1;其中 若ij,則dataidataj,1i,jn for (i=0; in; i+) data
6、j = 挑出datai至datan-1中最小者 swap(datai, dataj) / 將datai 和 dataj 對調 ,資料結構與演算法 徐熊健,1-10,程式1-1 挑選排序法:,void SelectionSort(int data, int n) int i, j; int min, temp; for (i=0; in; i+) min = i; for (j=i+1; jn; j+) if (datajdatamin) min = j; temp = datai; datai = datamin; datamin = temp; ,資料結構與演算法 徐熊健,1-11,程式的驗
7、証、測試與修繕,數學証明最佳的驗証;比較困難。 測試輸入大量各式資料測試之。 若此為提供他人的程式,還應考慮輸入正確性(input validation);若資料量非常大,則資料儲存用的陣列,宜用動態配置的技巧宣告使用,資料結構與演算法 徐熊健,1-12,1.4.2 遞迴演算法,直接遞迴 (direct recursion):當程序執行完成前呼叫了自己這個程序。 間接遞迴 (indirect recursion) :在程序執行完成前呼叫了其它會再度引用到自己的程序。 在設計遞迴程式時,切記終結條件 (termination condition) 的設立,否則易造形成無窮迴圈 。,程序呼叫時流程
8、的轉換,SS(int data,int n),void SS(int data,int n) ,資料結構與演算法 徐熊健,1-13,程式1-2 計算階乘,階乘的計算即可用遞迴的概念詮釋,請看: n! = n(n-1)! 於是可以寫一個計算階乘的程序 X(int n), 它接受傳入的整數 n,傳回 n*X(n-1),int X(int n) if (n = 1) return 1; return n*X(n-1); ,資料結構與演算法 徐熊健,1-14,程式1-3 產生排列,void perm (char c, int k, int n) / 產生 ck,.,cn-1 的所有排列 if (k =
9、 n-1) /終結條件成立時輸出此項排列 for (int i = 0; i n; i+) cout ci “ “; cout endl; else / 讓ck固定不動,求 perm(c, k+1, n) for (i=k; in; i+) /讓ckcn-1輪流當ck char temp=ck; ck=ci; ci=temp; perm(c,k+1,n); /產生ak+1,an-1的所有排列 temp=ck; ck=ci; ci=temp; /還原原字元順序 ,A B C D A B D C A C B D A C D B A D C B A D B C B A C D B A D C B C
10、 A D B C D A B D C A B D A C C B A D C B D A C A B D C A D B C D A B C D B A D B C A D B A C D C B A D C A B D A C B D A B C,資料結構與演算法 徐熊健,1-15,1.5 演算法的效率分析,什麼是有效率的演算法?電腦學家為此衡量準則提供了客觀的標準分析演算法的執行時間和記憶體需求。以時間複雜度或空間複雜度來討論演算法的效率 解決相同的問題,演算法所用的時間複雜度和空間複雜度愈少愈好。 時間複雜度(time complexity):一個程式或演算法所需的執行時間; 空間複雜度
11、(space complexity):一個程式或演算法所需的記憶體空間。,資料結構與演算法 徐熊健,1-16,1.5.1 演算法的執行次數,程式1-4 陣列元素加總 int Sum(int data,int n) int summation=0; for (int i=0; in; i+) summation += datai; return summation; ,程式1-5 陣列元素加總並計算所有指令執行的次數 int count = 0; / 全域變數宣告 count+; / 計算宣告 int 指令的執行 int Sum(int data,int n) int summation=0;
12、count+; / 計算宣告 int 指令的執行 for (int i=0; in; i+) count+; / 計算 for 指令的執行次數 summation += datai; count+; / 計算 = 指令的執行次數; count+; / 計算最後一次 for 指令的執行 count+; / 計算 return 指令的執行 return summation; ,程式1-4將傳入整數陣列data 中的n個元素 (data0datan-1),總加至整數變數summation中傳出。,在程式1-4中加入一全域變數count,來加總所有指令執行的次數;新的程式將如程式1-5所示。,資料結構
13、與演算法 徐熊健,1-17,1.5.1 演算法的執行次數(續),程式1-6 計算陣列元素加總所有指令執行的次數 count+; int Sum(int data,int n) count+; / 計算宣告 int 指令的執行 for (int i=0; in; i+) count += 2 count += 2; ,程式1-6 只保留程式1-5 的主體和加總count 的指令。 此程式的執行總次數為2n+4,其中 for 迴圈每執行一次,count會計數兩次;而迴圈共計有n次,所以for迴圈內即執行2n 次。,資料結構與演算法 徐熊健,1-18,1.5.2 演算法複雜度的表示方法:O、 和,假
14、設有兩個演算法都可解決問題P,其輸入資料量為n;演算法 A 的估算執行次數為 4n2+174,演算法 B 的估算執行次數為 n3+5n+6。(見下圖),在 n7 後 演算法 A 比 B 好,資料結構與演算法 徐熊健,1-19,用大O表示時間複雜度,f(n)指的是演算法的執行時間(步驟),我們希望能找到g(n);只要在nn0後,cg(n)一定會大於或等於f(n),那麼就可以用O(g(n)來表示f(n)。,定義:f (n)=O (g (n) 若且唯若存在兩個正整數c和n0,當nn0時,f (n) cg (n)。,資料結構與演算法 徐熊健,1-20,請注意在上圖中,當n 14 (=n0) 之後,cg
15、(n) 一定會大於或等於f(n)(5n2 4n2+174), 所以O(n2)足以代表4n2+174 。,資料結構與演算法 徐熊健,1-21,範例1-7,4n+12 = O(n),因為存在c=5,n0=12,使得n12後,4n+12 5n(或c=6,n0=6,使得n6後,4n+12 6n); 10n+25 = O(n),因為存在c=11,n0=13,使得n13後,10n+25 11n; 8n2+11n+18 = O(n2),因為存在c=9,n0=13,使得n13後,8n2+11n+18 9n2; 62n+n2 = O(2n),因為存在c=7,n0=4,使得n4後,62n+n2 72n;,資料結構
16、與演算法 徐熊健,1-22,範例1-7 (續),326 = O(1),因為存在c=327,n0可任取,使得n n0後,326 3271; 9n2+n+11 O(n),因為找不到適當的c和n0,使得nn0後,9n2+11 cn; 100n3 = O(n4),因為存在c=16,n0=8,使得n8後,100n3 16n4。,資料結構與演算法 徐熊健,1-23,以大O表示法分辨演算法的優劣,O(1)稱為常數時間,即不論演法的步驟須需要多少指令,只要不像迴圈般重複執行,皆視為常數時間; O(n)稱為線性時間,取其執行步驟的增加趨勢與n的增加趨勢為線性關係之意; O(n2)為平方時間;依此類推,而 O(2
17、n)則稱為指數時間。 如此一來,我們會說O(logn)的演算法比O(n)來得有效率,O(n)比O(n2)來得有效率。,資料結構與演算法 徐熊健,1-24,大O表示函數的優劣順序為: O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n)。,資料結構與演算法 徐熊健,1-25,大O的符號是為了方便討論演算法的複雜度而設計引用的; 則不然,它是為了方便討論問題的難易程度而設計引用的。其定義如下,假設f, g0:,定義:f (n)= (g (n) 若且唯若 存在兩個正整數c和n0,當nn0時, f (n)cg (n)。,用表示問題的難易程度,資料結構與演算法 徐熊健
18、,1-26,範例1-8,(a) 4n+12 = (n),因為存在c=1,n0=1,使得n1後,4n+12 n; (b) 10n+25 = (n),因為存在c=10,n0=1,使得n1後,10n+25 10n; (c) 8n2+11n+18 = (n2),因為存在c=1,n0=1,使得n1後,8n2+11n+18 n2; (d) 62n+n2 = (2n),因為存在c=1,n0=1,使得n1後,62n+n2 12n;,資料結構與演算法 徐熊健,1-27,範例1-8 (續),(e)326 = (1),因為存在c=1,n0可任取,使得nn0後,326 11; (f)9n2+n+11 (n3),因為找
19、不到適當的c和n0,使得nn0後,9n2+11 cn3; (g)100n3 = (n2) = (n) = (1),因為存在c=1,n0=,使得n1後,100n3 n2 n 1。,資料結構與演算法 徐熊健,1-28,最佳 (optimal) 演算法,定義:f (n) = (g (n) 若且唯若存在 參個正整數c1、c2和n0,當nn0時, c1g (n) f (n) c2g (n)。,如果既可找到演算法 A 來解決問題 P,時間複雜度為O(g(n),且又能証明解決問題 P 的最少代價亦為(g(n);則欲解決P的時間,至多要O(g(n),至少為(g(n);不可能比多於O(g(n),也不可能少於(g(n)(最多或最少都只是g(n)的常數倍),則演算法A是解決問題P的最佳 (optimal) 演算法。,資料結構與演算法 徐熊健,1-29,範例1-9,4n+12 = (n),因為存在c1=1、c2=5,n0=12,使得n12後,1n 4n+12 5n; 8n2+11n+18 = (n2),因為存在c1=1、c2=9,n0=13,使得n13後,1n2 8n2+11n+18 9n2。,
链接地址:https://www.31doc.com/p-3300473.html