目錄
1.常數時間的操作
2.時間復雜度
2.1.以選擇排序為例
2.2.O(n^2)從何而來
2.3.冒泡排序
2.3.1.抑或運算
2.4.插入排序
3.二分法
3.1.局部最小
4.遞歸
4.1.遞歸行為時間復雜度的估計
1.常數時間的操作
一個操作如果和樣本的數據量無關，每次都是固定時間內完成的操作，叫做常數操作
時間復雜度為一個算法流程中，常數數量的一個指標，常用O來表示。具體來說，先要對一個算法流程非常熟悉，然后去寫出這個算法流程中發生了多少次常數操作，進而總結出常數操作數量的表達式
在表達式中，只要高階項，不要低階項，也不要高階項的系數，剩下的部分如果為f(N)，那么時間復雜度為O(f(N))
評價一個算法流程的好壞，先看時間復雜度的指標，然后再分析不同樣本數據下的實際運行時間，也就是“常數項時間”
- 常數操作：int a = arr[i]; 或 +-*/ 或 位運算 等
- 非常數操作：int b = 鏈表.get(i);
2.時間復雜度
2.1.以選擇排序為例
時間復雜度O(N^2)，額外空間復雜度O(1)
設數組長度為N，我們遍歷N次，每次把遍歷到的最小值放在最左邊的位置上，同時把左邊界向右移動一位
我們每一次找出最小的數、次小的數、次次小的數...待尋找的區間不斷被壓縮
這是一種基礎且低效的查找方式，它的時間復雜度是O(n^2)
2.2.O(n^2)從何而來
數一數一共進行了多少次常數操作
第一次遍歷時，遍歷了N次，比較了N次，交換了1次
第二次遍歷時，遍歷了N-1次，比較了N-1次，交換了1次
......
遍歷：N + N-1 + N-2 + N-3 + ...
比較：N + N-1 + N-2 + N-3 + ...
swap：N次
三者相加 = aN^2 + bN + c只要高階項為N^2
2.3.冒泡排序
時間復雜度O(N^2)，額外空間復雜度O(1)
相鄰兩個數字進行比較，大的數字往右移，一共遍歷N-1次，第一次從第1個元素開始與相鄰后一個元素比較，直到第N-1個元素與第N個元素比較完為止，此時當前數組中最大的元素一定被排序到了最后一位。接著繼續遍歷前N-1個元素，第二次遍歷結束后，前N-1個元素的最大值一定被排序到了倒數第二位...
public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int e = arr.length-1; e > 0; e--) {for (int i = 0; i < e; i++) {if (arr[i] > arr[i+1]) {swap(arr, i, i+1);}}}
}//交換arr的i和j位置上的值
public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];
}2.3.1.抑或運算
相同為0，不同為1
抑或運算還可以理解為無進位相加
- 抑或運算的性質
(1) 0^N=N N^N=0
(2) 交換律：a^b = b^a
結合律：(a^b)^c = a^(b^c)
(3)同一批數進行抑或結果永遠相同
//怎么交換兩個數的值
a = a^b;
b = a^b; //即b = (a^b)^b = a^(b^b) = a^0 = a
a = a^b;a和b的值可以相等，但這樣做的前提是a與b在內存里是兩塊獨立的區域，在數組中兩個指針所指向的位置不能相同
- 與抑或有關的面試題
(1)
在一個數組中只有一種數出現了奇數次，其他的所有數都出現了偶數次，怎么找到出現了奇數次的數？要求時間復雜度O(N)，空間復雜度O(1)
答：
int eor = 0;
for (int cur : arr) {eor ^= cur;
}
return eor;(2) 在一個數組中只有兩種數出現了奇數次，其他的所有數都出現了偶數次，怎么找到出現了奇數次的數？要求時間復雜度O(N)，空間復雜度O(1)
- 為什么抑或運算滿足交換律與結合律
用“無進位相加”解釋：一組二進制數相加的結果與什么有關，與在某個二進制位上1的個數有關，與這些1出現的次序無關。在無進位相加時，偶數個1相加的結果是0，奇數個1相加的結果是1
//假設兩種出現奇數次的數是a、b，a!=b
int eor = 0;
for (int cur : arr) {eor ^= cur;
}
//eor == a^b != 0 => eor一定在某一位上等于1（int32位）
//假設eor的第x位為1
int eor_ = 0;
for (int cur : arr) {if (cur的第x位等于0) {eor_ ^= cur;}
}
//eor == a 或 eor == b 而另一個數則是eor^eor_現在的問題是，eor的第幾位是1？
我們選擇最右側的1
//找到eor最右側的1
int rightOne = eor & (~eor + 1);
//cur的第x位為0這樣表示
cur & rightOne == 0;
2.4.插入排序
時間復雜度O(N^2)，額外空間復雜度O(1)
一共排序N = arr.length次，第一次排序前1個數，第二次排序前2個數...每次都把當前范圍內最右邊的數向左移，直到左邊的數小于當前數字為止，此時該范圍內的數必定有序
???????
對于不同的數據，插入排序的時間復雜度不同
假如數據如下
時間復雜度為O(N^2)
假如數據如下
時間復雜度為O(N)
我們約定，時間復雜度是最壞情況下的算法表現，所以插入排序的時間復雜度是O(N^2)
public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 1; i < arr.length; i++) { //0~i做到有序for (int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--) {swap(arr, j, j+1);}}
}
?
public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];
}3.二分法
一個有序數組找某個數是否存在
如果遍歷，算法時間復雜度O(N)，沒有用到有序這一特性
我們每次將當前數組的中間位置元素與待查找元素比較，中間元素小，那就查找右側子數組，反之查找左側
每次查找都要“砍去”一半數組，數一數一共砍了幾次即可得到時間復雜度O(logN)
3.1.局部最小
無序也可以用二分
長度為N的數組，規定相鄰位置的元素一定不相等，如果0位置的數比1位置的數小，那么0位置的數是局部最小；如果N-1位置的數比N-2位置的數小，那么N-1位置的數為局部最小；對于中間位置i，如果i位置的數不僅比i-1位置的數小，而且比i+1位置的數小，那么i位置的數為局部最小。易得該數組必定存在至少一個局部最小
(1) 先看0位置的數是否小于1位置的數，若小則直接返回
(2) 看N-1位置的數是否小于N-2位置的數，若小則直接返回
(3) 我們取中點位置M，若[M] > [M-1]，則向左側子數組查找；若[M] < [M-1]且[M] > [M+1]，則向右側子數組查找；若都不滿足，則[M]為局部最小
4.遞歸
一道題引入遞歸
問：
找到一個數組的最大值
答：
不斷把當前數組拆成兩個子數組，返回兩個子數組的最大值中較大的那個
public static int getMax(int[] arr) {return process(arr, 0, arr.length-1);
}
?
public static int process(int[] arr, int L, int R) {if (L == R) {return arr[L];}int mid = L + ((R - l) >> 1);int leftMax = process(arr, L, mid);int rightMax = process(arr, mid+1, R);return Math.max(leftMax, rightMax);
}對該數組進行遞歸
畫出它的遞歸結構圖
把遞歸的過程理解為一棵多叉樹，每一個節點都通過子節點為自己匯總信息之后才能繼續往上返回，棧空間就是整棵樹的高度
4.1.遞歸行為時間復雜度的估計
- master公式
滿足子問題等規模的遞歸都可以用master公式求時間復雜度
T(N) = a*T(N/b) + O(N^d)
T(N)指的是母問題的數據量是N級別的
T(N/b)指的是子問題的規模都是N/b
a指的是子問題的調用次數
O(N^d)指的是除了調用子問題之外，剩下過程的時間復雜度
值得注意的是a/b未必等于1，因為以下式子同樣滿足master公式
T(N) = 2T(2N/3) + O(1)
結論：
logba < d ====> O(N^d)
logba > d ====> O(N^(logba))
logba == d ====> O((N^d)*logN)
