第十七課數(shù)據(jù)結(jié)構(gòu)（上）

1、第十七課：數(shù)據(jù)結(jié)構(gòu)(上),周甫 zoofchow@hotmail.com,www.ITjob.com,學(xué)習(xí)目標(biāo),www.ITjob.com,1 算法(algorithm),什么是算法?對一個現(xiàn)有的問題我們采取的解決過程及方法,即為算法. 一個用算法實現(xiàn)的程序會耗費兩種資源：處理時間和內(nèi)存。算法的效率分析標(biāo)準(zhǔn) 簡單性和清晰度空間效率時間效率,www.ITjob.com,,算法的類型貪婪算法(greedy algorit

2、hm) 分治算法(divide-and-conquer algorithm) 回溯算法(backtracking algorithm) 計算增長率的方式1.測量執(zhí)行時間通過System.currentTimeMillis()方法來測試 * 缺點：a.不同的平臺執(zhí)行的時間不同b.有些算法隨著輸入數(shù)據(jù)的加大，測試時間會變得不切實際！,www.ITjob.com,,2.指令計數(shù)指令---指編寫算法的代

3、碼.對一個算法的實現(xiàn)代碼計算執(zhí)行指令次數(shù)。兩種類型指令：不管輸入大小，執(zhí)行次數(shù)永遠(yuǎn)不變；執(zhí)行次數(shù)隨著輸入大小改變而改變。一般，我們主要測試后一種指令。*,www.ITjob.com,,3.代數(shù)計算代碼1：long end_time = 0;t1int testVar = 0;t2for (int i = 1; i <= test_data; i++) t

4、3{testVar++;t4testVar--;t4}假設(shè)t1 --- t4分別代表每條語句的執(zhí)行時間，那么，以上代碼的總執(zhí)行時間為：t1 + t2 + n(t3 + 2t4).其中n = test_data,當(dāng)test_data增大時，t1和t2可以忽略不計，也就是說，對于很大的n,執(zhí)行時間可以近似于：n(t3 + 2t4),www.ITjob.com,,4.測量內(nèi)存使用率

5、一個算法中包含的對象和引用的數(shù)目，越多則內(nèi)存使用越高，反之越低,www.ITjob.com,,比較增長率 1.代數(shù)比較法條件1：c≦ f(n)/g(n) ≦ d (其中c和d為正常數(shù)，n代表輸入大小)當(dāng)滿足以上條件1時，則f(n)和g(n)具備相同的增長率，或者兩函數(shù)復(fù)雜度的階相同！ 如：f(n) = n + 100 和 g(n) = 0.1n + 10 上兩函數(shù)就具備相同的增長率。條件2： 當(dāng)n增大時

6、，f(n)/g(n)趨向于0當(dāng)滿足此條件2時，則該兩個增長函數(shù)有不同的增長率。 比如：f(n) = 10000n + 20000 和 g(n) = n?2 + n + 1 。請比較以上兩函數(shù)增長率是否一樣，如果不一樣，誰的增長率小？,www.ITjob.com,,2.大O表示法 如果f的增長率小于或者等于g的增長率，則我們可以用如下的大O表示法：f = O(g)O表示on the order of將代

7、碼1的代數(shù)增長率函數(shù)的大O表達式如下：f(n) = t1 + t2 + n(t3 + 2t4) = a1*n + a = O(n)其中a1 = t3 + 2t4; a = t1 + t23.最佳、最差、平均性能對每一個算法不能只考慮單一的增長率，而應(yīng)該給出最佳、最差、平均的增長率函數(shù).,www.ITjob.com,2 查找算法,1.線性查找從數(shù)組的第一個元素開始查找，并將

8、其與查找值比較，如果相等則停止，否則繼續(xù)下一個元素查找，直到找到匹配值。注意：要求被查找的數(shù)組中的元素是無序的、隨機的。,www.ITjob.com,,static boolean linearSearch(int target, int[] array){//遍歷整個數(shù)組，并分別將每個遍歷元素與查找值對比for (int i = 0; i < array.length; i++)if (array[i

9、] == target)return true;return false;}分析該算法的三種情況：a.最佳情況要查找的值在數(shù)組的第一個位置。也就是說只需比較一次就可達到目的，因此最佳情況的大O表達式為：O(1)b.最差情況要查找的值在數(shù)組的末尾或者不存在，則對大小為n的數(shù)組必須比較n次，大O表達式為：O(n)c.平均情況估計會執(zhí)行：(n + (n - 1) + (n - 2)

10、+ ….. + 1)/n = (n + 1) / 2次比較，復(fù)雜度為O(n),www.ITjob.com,,2.二分查找假設(shè)被查找數(shù)組中的元素是升序排列的，那我們查找值時，首先會直接到數(shù)組的中間位置(數(shù)組長度/2)，并將中間值和查找值比較，如果相等則返回，否則，如果當(dāng)前元素值小于查找值，則繼續(xù)在數(shù)組的后面一半查找(重復(fù)上面過程)；如果當(dāng)前元素值大于查找值，則繼續(xù)在數(shù)組的前面一半查找，直到找到目標(biāo)值或者無法再二分?jǐn)?shù)組時停止。注意：

11、二分查找只是針對有序排列的各種數(shù)組或集合,www.ITjob.com,,static boolean binarySearch(int target, int[] array){int front = 0;int tail = array.length - 1;//判斷子數(shù)組是否能再次二分while (front target)tail = middle - 1;elsefront =

12、 middle + 1;}return false;},www.ITjob.com,,a.最佳情況：中間值為查找值，只需比較一次，復(fù)雜度為O(1)b.最差、平均：當(dāng)我們對一個數(shù)組執(zhí)行二分查找時，最多的查找次數(shù)是滿足n 20因此可以得出二分法的最差及平均情況的復(fù)雜度為O(logn)。,www.ITjob.com,課堂練習(xí),問題描述： 有一個有序數(shù)組:{1，2，3，4，5，6，7，8，9，10}，請分別：

13、 1、以線性法查找7的下標(biāo)。 2、以二分法查找4的下標(biāo)。,www.ITjob.com,3 排序算法,1 選擇排序首先在數(shù)組中查找最小值，如果該值不在第一個位置，那么將其和處在第一個位置的元素交換，然后從第二個位置重復(fù)此過程，將剩下元素中最小值交換到第二個位置。當(dāng)?shù)阶詈笠晃粫r，數(shù)組排序結(jié)束。,www.ITjob.com,,static int[] selectionSort(int[] arr){int tmp, s

14、mall;for(int i = 0; i < arr.length - 1; i++){small = i;for(int j = i + 1; j < arr.length; j++)if(arr[j] < arr[small])small = j;if(small != i){tmp = arr[i];arr[i] = arr[sma

15、ll];arr[small] = tmp;}print(arr);}return arr;}*,www.ITjob.com,課堂練習(xí),問題描述：對一個有10個元素的整數(shù)數(shù)組用選擇法排序,該數(shù)組元素由隨機數(shù)產(chǎn)生.,www.ITjob.com,,從上面代碼我們可以看出，假設(shè)數(shù)組大小為n，外循環(huán)共執(zhí)行n-1次；那么第一次執(zhí)行外循環(huán)時，內(nèi)循環(huán)將執(zhí)行n-1次；第二次執(zhí)行外循環(huán)時內(nèi)循環(huán)將執(zhí)行n-2次；最后一

16、次執(zhí)行外循環(huán)時內(nèi)循環(huán)將執(zhí)行1次，因此我們可以通過代數(shù)計算方法得出增長函數(shù)為：(n - 1) + (n - 2) + (n - 3) + ….. + 1 = n(n - 1) / 2 = 1/2 * n^2 + 1/2 * n，即可得出復(fù)雜度為：O(n^2)。我們可以分析得知，當(dāng)數(shù)組非常大時，用于元素交換的開銷也相當(dāng)大。這都屬于額外開銷，是呈線性增長的。注意：如果是對存儲對象的集合進行排序，則存儲對象必須實現(xiàn)Comparable接口，并

17、通過compareTo()方法來比較大小。,www.ITjob.com,,2 冒泡排序 從數(shù)組的第一個元素開始，每次比較一對元素，一直到數(shù)組結(jié)束，如果比較的這對元素順序不對，那么交換位置。這個過程會使數(shù)組中的最大(最小)元素逐漸冒到數(shù)組的最后(最前).,www.ITjob.com,,static int[] bubbleSort(int[] arr){int flag = 1, tmp;int n = arr.len

18、gth;for(int i = 1; i arr[j + 1]){flag = 1;tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}print(arr);}return arr;},www.ITjob.com,課堂練習(xí),問題描述：對一個有10個元素的整數(shù)數(shù)組用冒泡法排序,該數(shù)組元素由

19、隨機數(shù)產(chǎn)生.,www.ITjob.com,,3 插入排序和改良后的冒泡排序法類似，使用不同于冒泡的方法對數(shù)組進行部分排序！步驟如下：(假設(shè)數(shù)組長度為n)a.對數(shù)組的每次(第i次)循環(huán)，下標(biāo)值為i的元素應(yīng)該插入到數(shù)組的前i個元素的正確位置(如果是升序，則i元素應(yīng)插入到小于它的元素之后，大于它的元素之前，降序則反之)b.每次循環(huán)(第i次)結(jié)束時，應(yīng)保證前i個元素排序是正確的！c.包含兩個循環(huán)，外循環(huán)(循環(huán)變量為i)遍歷下

20、標(biāo)從0到n-1的元素，保存每次循環(huán)的所遍歷的元素的值，內(nèi)循環(huán)(循環(huán)變量為k)從i -1開始，即遍歷前將k賦值為i-1，每次k--，直到k < 0。在內(nèi)循環(huán)中，將第i個元素和該元素之前的所有元素一一對比，并將元素插入到合適的位置，如果第i個元素的位置是正確的，那么就跳出內(nèi)循環(huán)，重新開始外循環(huán)。,www.ITjob.com,,static void insertionSort(int[] array){for (int i =

21、0; i = 0){if (insert_item < array[k]){array[k + 1] = array[k];k--;}elsebreak;}array[k + 1] = insert_item;print(array);}},www.ITjob.com,,分析：內(nèi)循環(huán)在第一次外循環(huán)時執(zhí)行1次，第二次外循環(huán)時執(zhí)行2次，

22、。。。。第n - 1次外循環(huán)時執(zhí)行n - 1次，因此，插入排序的最差和平均情況的性能是O(n^2)。但是，在最佳情況下(即數(shù)組中的元素順序是完全正確的)，插入排序的性能是線性的。注意：插入排序適合針對于已排序元素多的數(shù)組，即數(shù)組中已排序的元素越多，插入排序的性能就越好。,www.ITjob.com,4 遞歸(recursive),何為遞歸?定義函數(shù)1：sum(1) = 1定義函數(shù)2：sum(n) = n + sum(n - 1

23、)假設(shè)n = 5，那么sum(5) = 5 + sum(4) =5 + 4 + sum(3) =5 + 4 + 3 + sum(2) =5 + 4 + 3 + 2 + sum(1) =5 + 4 + 3 + 2 + 1以上這種在自身中使用自身定義函數(shù)的過程稱之遞歸。,www.ITjob.com,,public class

24、Test{public static void main(String[] args){System.out.println("sum(5) = " + sum(5));}static int sum(int i){int count = 0;if(i == 1)return 1;elsecount = i + sum(i - 1);return count

25、;}},www.ITjob.com,,實現(xiàn)遞歸必須滿足兩個條件基本條件(base case)的成立實際上就是定義遞歸應(yīng)該什么時候終止遞歸步驟對于所有的n值，函數(shù)都是以其自身通過n值較小的函數(shù)來定義，也就是說，所有n值函數(shù)通過許多步驟來達到最終用n值較小的函數(shù)(基本條件)來定義?？梢缘弥f歸函數(shù)就是反復(fù)執(zhí)行遞歸步，直到n達到基本條件為止。 注意事項：----避免死循環(huán)，一般都是由于沒有基本條件而造成，也可能是遞歸

26、步的邏輯錯誤導(dǎo)致。,www.ITjob.com,,遞歸方法的運行實現(xiàn)原理我們發(fā)現(xiàn)，遞歸就是一個不停調(diào)用方法自身的一個過程，即方法的反復(fù)調(diào)用！計算機是通過棧的機制來實現(xiàn)方法調(diào)用的。首先，我們來了解下計算機的方法調(diào)用機制：1．程序執(zhí)行前，計算機會在內(nèi)存中創(chuàng)建一個調(diào)用棧 ，一般會比較大2．當(dāng)調(diào)用某個方法時，會有一個和該被調(diào)用方法相關(guān)的記錄信息被推入到棧中3．被推入到棧中的記錄信息包括內(nèi)容：傳遞到被調(diào)用方法中的參數(shù)值、該方法

27、的局部變量、該方法的返回值。4．當(dāng)返回某個方法或者方法結(jié)束時，會從棧中取出對應(yīng)的方法記錄信息棧的使用機制：后進先出(LIFO)。注意：最然遞歸方法簡潔，但是效率不是完全就比迭代高，有時甚至低。因為我們考慮算法不僅要從時間、增長率來考慮，還要考慮空間(一般指內(nèi)存)問題，遞歸的棧空間是我們必須考慮的，因為每次方法的調(diào)用都需額外的空間來存儲相關(guān)信息。,www.ITjob.com,獨立實踐,實踐 1對一個15個元素的隨機整數(shù)(0<

28、;=n<=100)數(shù)組中查找元素83的下標(biāo).(提示，先用冒泡法排序，然后2分法查找)實踐2 編寫遞歸實現(xiàn)5!實踐3 用遞歸實現(xiàn)10個數(shù)的菲波拉契數(shù)列實踐4 用遞歸法求任意2個整數(shù)的最大公約數(shù)(GCD)。提示：能夠同時被2個整數(shù)整除的最大整數(shù)，即為最大公約數(shù)。GCD(m,n)是n,若n小于等于m且n整除mGCD(m,n)是GCD(n,m)，若m小于nGCD(m,n)是GCD(n, m % n