時間複雜度
1、時間頻度
時間複雜度通常是衡量算法的優劣的，衡量算法的時間嚴格來講是很難衡量的，由于不同的機器性能不用環境都會造成不同的執行時間。算法的執行時間和語句的執行次數成正比，是以通過計算執行測試來推斷執行時間。算法中語句執行次數稱為語句頻度或時間頻度，記為T(n)，n是問題的規模，T是Time，即時間頻度。
2、時間複雜度
n不斷變化時，T(n)也在不斷變化，為了考察兩者變化時呈現什麼規律，可以使用時間複雜度來計算。
通常操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),存在一個正常數c使得f(n) * c >= T(n)恒成立。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。
簡言之，隻要計算一下語句的執行次數和n之間的關就可以了，去除系數部分，低階項目部分，就是時間複雜度的值了。
3、 時間複雜度的計算
3.1 給定任意長度數組，讀取數組第一個元素的值
無論數組長度n為多少，代碼執行一次。是以，時間複雜度為O(1)。
//無論數組的長度n為多少，
public void firstEle(int[] arr){
return arr[0] ; //代碼隻執行一次。
}
3.2 循環n次，輸出hello world
随着n的增大，列印函數逐漸增多。列印代碼執行的次數是n，是以時間複雜度為O(n)。
for(int i = 0 ; i < n ; i ++){
//執行一次。
System.out.println("hello world") ;
}
3.3 列印99乘法表
列印99正方乘法表，列印語句輸出9 * 9 = 81次。
列印語句執行次數：$$n * n = n2$$，是以時間複雜度是$$O(n2)$$
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= n ; j ++){
//列印語句的執行次數n * n次。
System.out.print(j + " x " + i + "=" + (i * j));
}
}
3.4 列印正三角的99乘法表
正三角形狀的99表格列印語句的執行次數為：
[1 + 2 + 3 + ... + n = (n + 1) dfrac{n}{2} = dfrac{n^2}{2} + dfrac{n}{2}
]
去掉系數部分和低階部分，時間複雜度為仍然為$$O(n^2)$$
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= i ; j ++){
//列印語句的執行次數n * n次。
System.out.print(j + " x " + i + "=" + (i * j));
}
}
3.5 冒泡排序
冒泡排序是經典的排序算法是每次比較相鄰的兩個元素進行對調，進行多輪，直到數列有序。
對于5個元素的冒泡排序來說，共需要比較4 + 3 + 2 + 1次比較。是以時間複雜度為：
[n - 1 + n - 2 + ... 1 = dfrac{(n-1)}{2}n = dfrac{n^2}{2} - dfrac{n}{2}
]
是以時間複雜度為：$$O(n^2)$$，這是冒泡排序最壞的情況下的時間複雜度。
int[] arr = ... ;
//外層比較n-1次
for(int i = 0 ; i < arr.length - 1 ; i ++){
//比較n-1-i次
for(int j = 0 ; j < arr.length -1 - i ; j ++){
int temp = arr[j] ;
if(arr[j] > arr[j + 1]){
arr[j] = arr[j + 1] ;
arr[j + 1] = temp ;
}
}
}
冒泡排序可以進行優化，在最好的情況下，複雜度為O(n)，思路如下：
設定标志位flag=1，表示整個數列已經有序，就不需要再排序了，在裡層循環中，如果發現沒有進行過資料交換，就說明數列已經有序。
在最好情況下，就是數列本身已經有序，隻需要執行外層的n-1次循環即可，是以複雜度為O(n)。
int[] arr = ... ;
//外層比較n-1次
for(int i = 0 ; i < arr.length - 1 ; i ++){
boolean flag = true ;
//比較n-1-i次
for(int j = 0 ; j < arr.length -1 - i ; j ++){
int temp = arr[j] ;
if(arr[j] > arr[j + 1]){
//發生交換，就設定标志位為false，即數列無序。
flag = false ;
arr[j] = arr[j + 1] ;
arr[j + 1] = temp ;
}
}
//判斷如果是數列有序，則終止循環。
if(flag){
break ;
}
}
3.6 折半查找
折半查找也叫二分查找，是高效的查找方式，前提條件是數列需要時有序數列。圖例如下：
代碼如下：
//有序數組
int[] arr = ... ;
int min = arr[0] ;
int max = arr[0] ;
int mid = arr[arr.length/2] ;
//目标元素
int targ = 3 ;
for(int min = 0 , max = arr.length - 1 ; min <= max ; ){
int mid = (min + max) / 2 ;
//命中了
if(arr[mid] == targ){
return mid ;
}
//落在右側範圍
else if(arr[mid] < targ){
min = mid + 1 ;
}
//落在左側範圍
else{
max = mid - 1 ;
}
}
折半查找的最壞時間複雜度為：以2為底，n的對數。
[O(log_2 n )
]
3.7 hashmap
哈希map是java中最重要的集合之一，設計非常巧妙，使用通過數組+連結清單方式組合實作，哈希的目的是讓對象在空間内盡可能分散。那麼HashMap的時間複雜度是多少呢？
如果hashmap的每個桶内的元素個數最多不會超過一個常數C，當增加元素時，不斷增加桶的數量，而保證每個桶内的元素量固定，是以就可以保證最快的查詢速度，則時間複雜度就是$$O(C*n^2)$$，去掉系數部分就是
[ O(n^0) = O(1)
]
如果在最壞的情況下就是所有元素進入同一個桶，導緻給桶内的鍊條非常長，則檢索資料時，時間複雜度為：
[ O(n)
]
3.8 矩陣的乘積
矩陣我們按照階數為n的兩個方陣進行計算，矩陣的乘法運算法則為：
[left|
egin{matrix}
a_{11} & a_{12} \
a_{21} & a_{22}
end{matrix}
ight|
*
left|
egin{matrix}
b_{11} & b_{12} \
b_{21} & b_{22}
end{matrix}
ight|
=
left|
egin{matrix}
a_{11} * b_{11}+a_{12} *b_{21} &a_{11} * b_{12}+a_{12} *b_{22} \
a_{21} * b_{11}+a_{22} *b_{21} &a_{21} * b_{12}+a_{22} *b_{22}
end{matrix}
ight|
]
例如：
[left|
egin{matrix}
0 & 1 \
1 & 1 \
end{matrix}
ight|
*
left|
egin{matrix}
1 & 2 \
3 & 4 \
end{matrix}
ight|
=
left|
egin{matrix}
0*1+1*3 & 0*2+1*4 \
1*1+1*3 & 1*2+1*4 \
end{matrix}
ight|
=
left|
egin{matrix}
3 &4 \
4 & 6 \
end{matrix}
ight|
]
方陣乘法的代碼如下：
//方陣使用二位數組表示
int[][] a = ... ;
int[][] b = ... ;
//結果矩陣
int[][] r = ... ;
//[思路]
//從結果矩陣出發，結果矩陣也是一個階數為n的方陣，但是每個對應的元素
//循環n次計算累加和得到。
//循環行數
for(int i = 0 ; i < a.length ; i ++){
//循環列的個數，這裡仍然是m.length是因為方陣
for(int j = 0 ; j < b.length ; j ++){
for(int k = 0 ; k < a.length ; k ++){
r[i][j] = r[i][j] + a[i][k] * b[k][j] ;
}
}
}
方陣的矩陣乘法的計算次數為$$n3$$，是以時間複雜度為$$O(n3)$$。