為什么要復雜度分析境氢？
- 不依賴測試環(huán)境
- 不受數(shù)據(jù)量影響
大 O 復雜度表示法
算法執(zhí)行效率
算法代碼執(zhí)行時間
復雜度公式 T(n)=O(f(n))
解釋：
- T(n) 表示代碼執(zhí)行時間轮洋，n 表示數(shù)據(jù)規(guī)模大小
- f(n) 表示每行代碼執(zhí)行的次數(shù)總和
- O 表示代碼的執(zhí)行時間 T(n) 和 f(n) 表達式成正比
大 O 時間復雜度實際上并不代表代碼真正的執(zhí)行時間而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢枉氮，所以也叫 漸進時間復雜度志衍，簡稱 時間復雜度
時間復雜度分析
- 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
- 加法法則：總復雜度等于量級最大的那段代碼的時間復雜度
- 乘法法則：嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積
O(1)
- 是常量級時間復雜度的一種表達方法，不是只執(zhí)行了一行代碼
- 只要算法中不存在循環(huán)語句嘲恍、遞歸語句足画，即使有成千上萬行代碼，時間復雜度也是 O(1)
int i = 8;
int j = 6;
int sum = i + j;
O(logn)佃牛、O(nlogn)
i=1;
while (i <= n) {
i = i * 2;
}
變量 i 的值從1開始淹辞，每循環(huán)一次就乘以2。當大于 n 時俘侠，循環(huán)結(jié)束象缀。
所以 i 的值是
image.png
image.png
日常用語：n以2為低的對數(shù)是x，意思是 2的x次方等于n
O(m+n)爷速、O(m*n)
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
- m,n 是表示兩個數(shù)據(jù)規(guī)模央星，無法事先評估 m 和 n 誰的量級大所以在表示復雜度的時候就不能利用加法法則省略一個了所以是O(m+n)
- 如果是兩個數(shù)據(jù)規(guī)模的嵌套循環(huán)，那么時間復雜度就是 O(m*n)
空間復雜度分析
- 空間復雜度全稱是漸進空間復雜度惫东，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系
- 常見空間復雜度 O(1)莉给、O(n)、O(n^2)
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
跟時間復雜度分析一樣廉沮，我們可以看到颓遏，第 2 行代碼中，我們申請了一個空間存儲變量 i滞时，但是它是常量階的叁幢，跟數(shù)據(jù)規(guī)模 n 沒有關(guān)系，所以我們可以忽略坪稽。第 3 行申請了一個大小為 n 的 int 類型數(shù)組曼玩，除此之外，剩下的代碼都沒有占用更多的空間窒百，所以整段代碼的空間復雜度就是 O(n)黍判。
越高階復雜度的算法，執(zhí)行效率越低
從低階到高階：O(1)篙梢、O(logn)顷帖、O(n)、O(nlogn)、O(n^2)
image.png
最好窟她、最壞情況時間復雜度
- 最好情況時間復雜度：最理想的情況下，執(zhí)行代碼的時間復雜度（比如蔼水，在循環(huán)中震糖，第一個就是你要查找的元素）
- 最壞情況時間復雜度：最糟糕的情況下，執(zhí)行代碼的時間復雜度（比如趴腋，在循環(huán)中吊说，沒有你要查找的元素）
-
平均情況時間復雜度：我們要查找的元素在數(shù)組中的位置有 n+1 中情況，在數(shù)組的 0～n-1 位置中和不在數(shù)組中优炬，把每種情況下颁井，查找需要遍歷的元素個數(shù)累加起來，然后除以 n+1蠢护，就可以得到需要遍歷的元素個數(shù)平均值image.png
用大 O 標記法雅宾，省略掉系數(shù)、低價葵硕、常量眉抬，所以得到平均復雜度為 O(n)
- 均攤情況時間復雜度：
只有在特殊情況下,我們才需要分析一段代碼的三種復雜度. 這種特殊情況就是: 同一個代碼塊在不同的情況下,時間復雜度有量級的差距. 這個時候我們才會采用 最好時間復雜度, 最壞時間復雜度,平均時間復雜度來 表示該段代碼的時間復雜度.
image
