• 數(shù)學(xué)模型
  • 1. 近似
  • 2. 增長數(shù)量級
  • 3. 內(nèi)循環(huán)
  • 4. 成本模型
• 注意事項
  • 1. 大常數(shù)
  • 2. 緩存
  • 3. 對最壞情況下的性能的保證
  • 4. 隨機化算法
  • 5. 均攤分析
• ThreeSum
  • 1. ThreeSumSlow
  • 2. ThreeSumBinarySearch
  • 3. ThreeSumTwoPointer
• 倍率實驗

數(shù)學(xué)模型

1. 近似

N³/6-N²/2+N/3 ~ N³/6。使用 ~f(N) 來表示所有隨著 N 的增大除以 f(N) 的結(jié)果趨近于 1 的函數(shù)。

2. 增長數(shù)量級

N³/6-N²/2+N/3 的增長數(shù)量級為 O(N³)。增長數(shù)量級將算法與它的具體實現(xiàn)隔離開來，一個算法的增長數(shù)量級為 O(N³) 與它是否用 Java 實現(xiàn)，是否運行于特定計算機上無關(guān)。

3. 內(nèi)循環(huán)

執(zhí)行最頻繁的指令決定了程序執(zhí)行的總時間，把這些指令稱為程序的內(nèi)循環(huán)。

4. 成本模型

使用成本模型來評估算法，例如數(shù)組的訪問次數(shù)就是一種成本模型。

注意事項

1. 大常數(shù)

在求近似時，如果低級項的常數(shù)系數(shù)很大，那么近似的結(jié)果是錯誤的。

2. 緩存

計算機系統(tǒng)會使用緩存技術(shù)來組織內(nèi)存，訪問數(shù)組相鄰的元素會比訪問不相鄰的元素快很多。

3. 對最壞情況下的性能的保證

在核反應(yīng)堆、心臟起搏器或者剎車控制器中的軟件，最壞情況下的性能是十分重要的。

4. 隨機化算法

通過打亂輸入，去除算法對輸入的依賴。

5. 均攤分析

將所有操作的總成本除于操作總數(shù)來將成本均攤。例如對一個空棧進(jìn)行 N 次連續(xù)的 push() 調(diào)用需要訪問數(shù)組的次數(shù)為 N+4+8+16+…+2N=5N-4（N 是向數(shù)組寫入元素的次數(shù)，其余都是調(diào)整數(shù)組大小時進(jìn)行復(fù)制需要的訪問數(shù)組次數(shù)），均攤后訪問數(shù)組的平均次數(shù)為常數(shù)。

ThreeSum

ThreeSum 用于統(tǒng)計一個數(shù)組中和為 0 的三元組數(shù)量。

public interface ThreeSum {int count(int[] nums); }

1. ThreeSumSlow

該算法的內(nèi)循環(huán)為 if (nums[i] + nums[j] + nums[k] == 0) 語句，總共執(zhí)行的次數(shù)為 N(N-1)(N-2) = N³/6-N²/2+N/3，因此它的近似執(zhí)行次數(shù)為 ~N³/6，增長數(shù)量級為 O(N³)。

public class ThreeSumSlow implements ThreeSum {@Overridepublic int count(int[] nums) {int N = nums.length;int cnt = 0;for (int i = 0; i < N; i++) {for (int j = i + 1; j < N; j++) {for (int k = j + 1; k < N; k++) {if (nums[i] + nums[j] + nums[k] == 0) {cnt++;}}}}return cnt;} }

2. ThreeSumBinarySearch

將數(shù)組進(jìn)行排序，對兩個元素求和，并用二分查找方法查找是否存在該和的相反數(shù)，如果存在，就說明存在和為 0 的三元組。

應(yīng)該注意的是，只有數(shù)組不含有相同元素才能使用這種解法，否則二分查找的結(jié)果會出錯。

該方法可以將 ThreeSum 算法增長數(shù)量級降低為 O(N²logN)。

public class ThreeSumBinarySearch implements ThreeSum {@Overridepublic int count(int[] nums) {Arrays.sort(nums);int N = nums.length;int cnt = 0;for (int i = 0; i < N; i++) {for (int j = i + 1; j < N; j++) {int target = -nums[i] - nums[j];int index = BinarySearch.search(nums, target);// 應(yīng)該注意這里的下標(biāo)必須大于 j，否則會重復(fù)統(tǒng)計。if (index > j) {cnt++;}}}return cnt;} } public class BinarySearch {public static int search(int[] nums, int target) {int l = 0, h = nums.length - 1;while (l <= h) {int m = l + (h - l) / 2;if (target == nums[m]) {return m;} else if (target > nums[m]) {l = m + 1;} else {h = m - 1;}}return -1;} }

3. ThreeSumTwoPointer

更有效的方法是先將數(shù)組排序，然后使用雙指針進(jìn)行查找，時間復(fù)雜度為 O(N²)。

同樣不適用與數(shù)組存在重復(fù)元素的情況。

public class ThreeSumTwoPointer implements ThreeSum {@Overridepublic int count(int[] nums) {int N = nums.length;int cnt = 0;Arrays.sort(nums);for (int i = 0; i < N - 2; i++) {int l = i + 1, h = N - 1, target = -nums[i];while (l < h) {int sum = nums[l] + nums[h];if (sum == target) {cnt++;l++;h--;} else if (sum < target) {l++;} else {h--;}}}return cnt;} }

倍率實驗

如果 T(N) ~ aN^blogN，那么 T(2N)/T(N) ~ 2^b。

例如對于暴力的 ThreeSum 算法，近似時間為 ~N³/6。進(jìn)行如下實驗：多次運行該算法，每次取的 N 值為前一次的兩倍，統(tǒng)計每次執(zhí)行的時間，并統(tǒng)計本次運行時間與前一次運行時間的比值，得到如下結(jié)果：

NTime(ms)Ratio

500	48	/
1000	320	6.7
2000	555	1.7
4000	4105	7.4
8000	33575	8.2
16000	268909	8.0

可以看到，T(2N)/T(N) ~ 2³，因此可以確定 T(N) ~ aN³logN。

public class RatioTest {public static void main(String[] args) {int N = 500;int loopTimes = 7;double preTime = -1;while (loopTimes-- > 0) {int[] nums = new int[N];StopWatch.start();ThreeSum threeSum = new ThreeSumSlow();int cnt = threeSum.count(nums);System.out.println(cnt);double elapsedTime = StopWatch.elapsedTime();double ratio = preTime == -1 ? 0 : elapsedTime / preTime;System.out.println(N + " " + elapsedTime + " " + ratio);preTime = elapsedTime;N *= 2;}} } public class StopWatch {private static long start;public static void start() {start = System.currentTimeMillis();}public static double elapsedTime() {long now = System.currentTimeMillis();return (now - start) / 1000.0;} }

總結(jié)

以上是生活随笔為你收集整理的【精品计划 附录2】- 算法分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。