第十七課：數(shù)據(jù)結構（上）-文庫吧
2025-08-25 13:04 本頁面
【正文】 將代碼 1的代數(shù)增長率函數(shù)的大 O表達式如下： f(n) = t1 + t2 + n(t3 + 2t4) = a1*n + a = O(n) 其中 a1 = t3 + 2t4。 a = t1 + t2 ? 、最差、平均性能 對每一個算法不能只考慮單一的增長率，而應該給出最佳、最差、平均的增長率函數(shù) . 2 查找算法 ? 從數(shù)組的第一個元素開始查找，并將其與查找值比較，如果相等則停止，否則繼續(xù)下一個元素查找，直到找到匹配值。 注意：要求被查找的數(shù)組中的元素是無序的、隨機的。 static boolean linearSearch(int target, int[] array) { //遍歷整個數(shù)組，并分別將每個遍歷元素與查找值對比 for (int i = 0。 i 。 i++) if (array[i] == target) return true。 return false。 } 分析該算法的三種情況： 要查找的值在數(shù)組的第一個位置。也就是說只需比較一次就可達到目的，因此最佳情況的大 O表達式為： O(1) 要查找的值在數(shù)組的末尾或者不存在，則對大小為 n的數(shù)組必須比較 n次，大O表達式為： O(n) 估計會執(zhí)行： (n + (n 1) + (n 2) + ….. + 1)/n = (n + 1) / 2 次比較，復雜度為O(n) ? 假設被查找數(shù)組中的元素是升序排列的，那我們查找值時，首先會直接到數(shù)組的中間位置 (數(shù)組長度 /2)，并將中間值和查找值比較，如果相等則返回，否則，如果當前元素值小于查找值，則繼續(xù)在數(shù)組的后面一半查找 (重復上面過程 )；如果當前元素值大于查找值，則繼續(xù)在數(shù)組的前面一半查找，直到找到目標值或者無法再二分數(shù)組時停止。 注意：二分查找只是針對有序排列的各種數(shù)組或集合 static boolean binarySearch(int target, int[] array){ int front = 0。 int tail = 1。 //判斷子數(shù)組是否能再次二分 while (front = tail){ //獲取子數(shù)組的中間位置，并依據(jù)此中間位置進行二分 int middle = (front + tail) / 2。 if (array[middle] == target) return true。 else if (array[middle] target) tail = middle 1。 else front = middle + 1。 } return false。 } ： 中間值為查找值，只需比較一次，復雜度為O(1) 、平均：
教學課件相關推薦
鄂ICP備17016276號-1