事后統(tǒng)計(jì)法
測(cè)試結(jié)果非常依賴(lài)測(cè)試環(huán)境
測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大
大 O 復(fù)雜度表示法
大O符號(hào)
大O符號(hào)（英語(yǔ)：Big O notation）膝宁，又稱(chēng)為漸進(jìn)符號(hào)跨晴，是用于描述函數(shù)漸近行為的數(shù)學(xué)符號(hào)欧聘。更確切地說(shuō)，它是用另一個(gè)（通常更簡(jiǎn)單的）函數(shù)來(lái)描述一個(gè)函數(shù)數(shù)量級(jí)的漸近上界端盆。
大O符號(hào)是由德國(guó)數(shù)論學(xué)家保羅·巴赫曼在其1892年的著作《解析數(shù)論》（Analytische Zahlentheorie）首先引入的树瞭。而這個(gè)記號(hào)則是在另一位德國(guó)數(shù)論學(xué)家艾德蒙·朗道的著作中才推廣的，因此它有時(shí)又稱(chēng)為朗道符號(hào)（Landau symbols）爱谁。代表“order of ...”（……階）的大O晒喷，最初是一個(gè)大寫(xiě)希臘字母“Ο”（omicron），現(xiàn)今用的是大寫(xiě)拉丁字母“O”访敌。
大 O 時(shí)間復(fù)雜度
大 O 時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間凉敲，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，所以寺旺，也叫作漸進(jìn)時(shí)間復(fù)雜度爷抓，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。
怎么計(jì)算時(shí)間復(fù)雜度
Tn = O(f(n))
而公式中的低階阻塑、常量蓝撇、系數(shù)三部分并不左右增長(zhǎng)趨勢(shì)，所以都可以忽略陈莽。我們只需要記錄一個(gè)最大量級(jí)就可以了
只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
常見(jiàn)時(shí)間復(fù)雜度實(shí)例分析
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;
while (i <= n) {
i = i * 3;
}
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;
}
最好、最壞独柑、平均迈窟、均攤時(shí)間復(fù)雜度
同一段代碼在不同情況下時(shí)間復(fù)雜度會(huì)出現(xiàn)量級(jí)差異，為了更全面忌栅，更準(zhǔn)確的描述代碼的時(shí)間復(fù)雜度车酣，所以引入這4個(gè)概念。
最好：最理想的情況下
最壞：在最糟糕的情況下
平均：加權(quán)平均時(shí)間復(fù)雜度
均攤：一種特殊的索绪，通過(guò)攤還分析得到的平均時(shí)間復(fù)雜度
時(shí)間復(fù)雜度表示
O：big-O————上界
Ω：big-Omega—–下界（很少用）
Θ：big-Theta——-確界
為什么見(jiàn)周?chē)嗣枋鏊惴◤?fù)雜度都用大 O 符號(hào)而不是大 Θ?
示例：find
// n 表示數(shù)組 array 的長(zhǎng)度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
最好：Ω(1)
最壞：O(n)
平均：O(n)
攤還分析法：將較高時(shí)間復(fù)雜度那次操作的耗時(shí)湖员，平攤到其他那些時(shí)間復(fù)雜度比較低的操作上。適用于低級(jí)別和高級(jí)別復(fù)雜度出現(xiàn)具有時(shí)序規(guī)律瑞驱。均攤結(jié)果一般都等于低級(jí)別復(fù)雜度破衔。
示例：insert
// array 表示一個(gè)長(zhǎng)度為 n 的數(shù)組
// 代碼中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
最好：Ω(1)
最壞：O(n)
平均：O(1)
能夠應(yīng)用均攤時(shí)間復(fù)雜度分析的場(chǎng)合，一般均攤時(shí)間復(fù)雜度就等于最好情況時(shí)間復(fù)雜度
常見(jiàn)排序算法的時(shí)間復(fù)雜度
| 排序算法 | 最佳時(shí)間復(fù)雜度 | 平均時(shí)間復(fù)雜度 | 最壞時(shí)間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|---|
| 選擇排序 | O(N^2) | O(N^2) | O(N^2) | 不穩(wěn)定 |
| 插入排序 | O(N) | O(N^2) | O(N^2) | 穩(wěn)定 |
| 冒泡排序 | O(N) | O(N^2) | O(N^2) | 穩(wěn)定 |
| 希爾排序 | O(N) | O(NlogN) | O(N^S)（1<S<2） | 不穩(wěn)定 |
| 快速排序 | O(NlogN) | O(NlogN) | O(N^2) | 不穩(wěn)定 |
| 堆排序 | O(NlogN) | O(NlogN) | O(NlogN) | 不穩(wěn)定 |
| 歸并排序 | O(NlogN) | O(NlogN) | O(NlogN) | 穩(wěn)定 |
空間復(fù)雜度
漸進(jìn)空間復(fù)雜度钱烟，表示算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系晰筛。
是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度
func TestRoom(t *testing.T) {
var n int = 10000
var list = new([1000]int)
for i := 0; i < n; i++ {
list[i%1000] = i
fmt.Println(i%1000, i)
}
}
//?
func TestRoom2(t *testing.T) {
var n int = 10000
var list []int
for i := 0; i < n; i++ {
list = append(list, i)
}
}
引用：
https://blog.csdn.net/qq_35556064/article/details/82888717
https://blog.csdn.net/Michael__Jack/article/details/71075459
極客時(shí)間: https://time.geekbang.org/column/article/41149
https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
