第十七課數據結構（上）

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

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

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

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

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

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

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

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

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

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

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

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

13、 1、以線性法查找7的下標。 2、以二分法查找4的下標。,www.ITjob.com,3 排序算法,1 選擇排序首先在數組中查找最小值，如果該值不在第一個位置，那么將其和處在第一個位置的元素交換，然后從第二個位置重復此過程，將剩下元素中最小值交換到第二個位置。當到最后一位時，數組排序結束。,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,課堂練習,問題描述：對一個有10個元素的整數數組用選擇法排序,該數組元素由隨機數產生.,www.ITjob.com,,從上面代碼我們可以看出，假設數組大小為n，外循環(huán)共執(zhí)行n-1次；那么第一次執(zhí)行外循環(huán)時，內循環(huán)將執(zhí)行n-1次；第二次執(zhí)行外循環(huán)時內循環(huán)將執(zhí)行n-2次；最后一

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

17、通過compareTo()方法來比較大小。,www.ITjob.com,,2 冒泡排序 從數組的第一個元素開始，每次比較一對元素，一直到數組結束，如果比較的這對元素順序不對，那么交換位置。這個過程會使數組中的最大(最小)元素逐漸冒到數組的最后(最前).,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,課堂練習,問題描述：對一個有10個元素的整數數組用冒泡法排序,該數組元素由

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

20、標從0到n-1的元素，保存每次循環(huán)的所遍歷的元素的值，內循環(huán)(循環(huán)變量為k)從i -1開始，即遍歷前將k賦值為i-1，每次k--，直到k < 0。在內循環(huán)中，將第i個元素和該元素之前的所有元素一一對比，并將元素插入到合適的位置，如果第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,,分析：內循環(huán)在第一次外循環(huán)時執(zhí)行1次，第二次外循環(huán)時執(zhí)行2次，

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

23、)假設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以上這種在自身中使用自身定義函數的過程稱之遞歸。,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,,實現遞歸必須滿足兩個條件基本條件(base case)的成立實際上就是定義遞歸應該什么時候終止遞歸步驟對于所有的n值，函數都是以其自身通過n值較小的函數來定義，也就是說，所有n值函數通過許多步驟來達到最終用n值較小的函數(基本條件)來定義。可以得知，遞歸函數就是反復執(zhí)行遞歸步，直到n達到基本條件為止。 注意事項：----避免死循環(huán)，一般都是由于沒有基本條件而造成，也可能是遞歸

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

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

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