認識時間復雜度
常數(shù)時間的操作：一個操作如果和數(shù)據(jù)量沒有關系，每次都是固定時間內完成的操作，叫做常數(shù)操作。
常數(shù)時間的操作符合兩點：
- 一次操作的時間與數(shù)量級沒有關系。
- 每次操作花費的時間是確定有限的。
時間復雜度為一個算法流程中，常數(shù)操作數(shù)量的指標。常用O（讀作bigO）來表示。具體來說，在常數(shù)操作數(shù)量的表達式中，只要高階項，不要低階項，也不要高階項的系數(shù)，剩下的部分如果記為f(N)，那么時間復雜度為O(f(N))。
如果一個算法的時間復雜度是 a*N^2 + b*N + c，那么 a*N^2 就是高階項，b*N為低階項，c為常數(shù)項。不要低階項就是拋除 b*N + c ，只留下最高階 a*N^2；也不要高階項的系數(shù)就是拋除系數(shù)a，最后的結果為 N^2，所以這個算法的時間復雜度為 O(N^2)。
評價一個算法流程的好壞，先看時間復雜度的指標，然后再分析不同數(shù)據(jù)樣本下的實際運行時間，也就是常數(shù)項時間。
常用的時間復雜度按照耗費的時間從小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2?)<O(n!)
對數(shù)器的概念和使用
對數(shù)器是用來測試代碼正確性的，我們在找不到合適的oj系統(tǒng)測試自己的代碼時，可以自己寫一個對數(shù)器對代碼進行測試。
1，有一個你想要測的方法A
比如我寫了一個排序算法A，需要檢測是否正確。
public static void bubbleSort(int[] arr){
if(arr == null || arr.length == 0){
return;
}
for(int end = arr.length - 1; end > 0; end--){
for(int i = 0; i < end; i++){
if(arr[i] > arr[i + 1]){
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
2，實現(xiàn)一個絕對正確但是復雜度不好的方法B
這里使用系統(tǒng)的排序算法保證算法的正確性。
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
3，實現(xiàn)一個隨機樣本產(chǎn)生器
這個方法產(chǎn)生一個最大長度maxSize和最大值maxValue的隨機數(shù)組，作為一次隨機樣本。
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
4，實現(xiàn)比對的方法
對比我需要檢測的方法A和絕對正確的方法B所產(chǎn)生的結果是否相同。
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
5，把方法A和方法B比對很多次來驗證方法A是否正確。
采取大量隨機樣本對比，這里使用了50萬個隨機樣本進行對比。
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
bubbleSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
bubbleSort(arr);
printArray(arr);
}
6，如果有一個樣本使得比對出錯，打印樣本分析是哪個方法出錯
7，當樣本數(shù)量很多時比對測試依然正確，可以確定方法A已經(jīng)正確。
遞歸行為的時間復雜度
遞歸的本質就是用壓棧與出棧操作。
當遞歸操作需要執(zhí)行子遞歸操作時，會將當前執(zhí)行的所有數(shù)據(jù)壓入棧中，這些數(shù)據(jù)包括當前跑到多少行，當前的參數(shù)和函數(shù)內的參數(shù)變量等等。
當子遞歸操作返回時進行出棧操作，然后讀取出棧后棧頂空間的信息，也就是返回到當初調用的地方。
遞歸行為時間復雜度的計算
一般的空間復雜度可以使用master公式計算：
master公式 : T(N) = a * T(N / b) + O(N ^ d)
T(N)：父問題的樣本量
a：調用模塊發(fā)生的次數(shù)
T(N/b)：子問題的樣本量
O(N^d)：除去子問題調用過程外，剩下部分的時間復雜度
1) log(b,a) > d -> 復雜度為O(N^log(b,a))
2) log(b, a) = d -> 復雜度為O(N^d * logN)
2) log(b, a) < d -> 復雜度為O(N^d)
我們使用遞歸二分求最大數(shù)來舉例：
/*
* 遞歸二分求最大數(shù)
*/
public static int getMaxNum(int[] arr, int L, int R) {
// 遞歸結束條件：只剩下一個數(shù)
if(L == R)
return arr[L];
int mid = L +((R - L) >> 1); //位運算取中值
int leftMax = getMaxNum(arr, L, mid); //T(N/2)
int rightMax = getMaxNum(arr, mid + 1, R); //T(N/2)
return Math.max(leftMax, rightMax); //O(1)
}
遞歸邊界：當整個數(shù)組被分割成只有一個數(shù)時結束遞歸。
遞歸邏輯：將數(shù)組從中間分割為兩個數(shù)組，分別取出左右兩個數(shù)組的最大值，再對比這兩個值取最大值。而分割出來的每個數(shù)組又繼續(xù)分割為兩個數(shù)組，直到分割出來的數(shù)組只有一個數(shù)為止。
遞歸時間復雜度的計算：
master公式：T(N) = a * T(N / b) + O(N ^ d)
a：調用模塊發(fā)生的次數(shù)，這里左右兩邊各執(zhí)行了一次，a = 2；
b：T(N/b)為子問題的樣本量，數(shù)組從中間分為相等兩份，b = 2；
d：O(N^d)為剩下部分的時間復雜度，這里只執(zhí)行了取中間值和比較最大值的兩個操作，都為常數(shù)操作，d = 0；
套用公式以后：T(N) = 2 * T(N / 2) + O(N ^ 0)
滿足：log(b,a) > d -> 復雜度為O(N^log(b,a))
時間復雜度即為：O(N^1) = O(N)
參考資料：牛客網(wǎng)左程云初級算法教程
