概述
尴尬，學妹問我“冒泡排序、二分查找、希爾排序、快速排序方法”算法的『時間複雜度』，我隻能使用百度查詢答案進行了回答，但這不符合我的人設，我必須要弄懂這個東西。
作為一個「不稱職的攻城獅」，對複雜度的概念是很模糊的，更不要說去計算複雜度了。
但是在開發中對于代碼快的執行，做到“提高代碼執行率、降低記憶體占用率”，巧了，這和我百度了解到的『複雜度』相似，然後查詢了相關資料，進行一個複習歸納。
簡單來說，就是同一個功能：
- 别人寫出來運作，記憶體占用100M，運作時間需要1秒；
- 自己寫出來運作，記憶體占用500M，運作時間需要5秒。
這你能忍？但是在代碼開發中是沒辦法計算記憶體占用和運作時間情況的，怎麼樣才能預估代碼塊達到了較優呢？而且在不同的裝置上執行的效果也不同，
比如你新買的手機和用了5年的手機，打開同一個軟體所需要的時間肯定是不同的。
但是我們基本的代碼塊運作次數是可以計算的，這就是我們今天的主角『複雜度』。
PS：衡量不同算法之間的優劣就要用到時間複雜度和空間複雜度。
時間複雜度
什麼是時間複雜度？舉個例子：
public string attack(int n)
{
for (int i = 0; i < n; i++)
{
Console.WriteLine("被攻擊");
}
return "快來救我";
} 上面代碼執行如下：
i = 0 : 執行 1 次
i < n : 執行 n+1 次
i++ : 執行 n+1 次
Console.WriteLine("被攻擊"); : 執行 n 次
return "快來救我" : 執行 1 次 這個方法的總執行次數就是 3n + 4 次，
但是開發過程中不可能都這樣去數，是以根據代碼執行時間推導過程就有一個規律，這就是所有代碼執行時間 T(n)和代碼的執行次數 f(n) ，這個是成正比的，而這個規律有一個公式（大歐表示法）：
T(n) = O(f(n))
n 是輸入資料的大小或者輸入資料的數量
T(n) 表示一段代碼的總執行時間
f(n) 表示一段代碼的總執行次數
O 表示代碼的執行時間 T(n) 和 執行次數f(n) 成正比 套用公式可以得到上面方法的複雜度就是：O(3n+4)，簡化為O(n)。
為什麼可以簡化為O(n)呢，我們看下簡化過程。
- 如果隻是常數直接估算為1，O(3) 的時間複雜度就是 O
(1)
- O(3n+4) 裡常數4對于總執行次數的幾乎沒有影響，直接忽略不計，系數 3 影響也不大，因為3n和n都是一個量級的，是以作為系數的常數3也估算為1或者可以了解為去掉系數，是以 O(3n+4) 的時間複雜度為 O
(n)
- 如果是多項式，隻需要保留n的最高次項，O
( 666n³ + 666n² + n )
時間複雜度為 O(n³)
是不是很簡單，我們看下常用的時間複雜度。
1、常數階 O(1)
通過上面的簡化過程知道，一般情況下，隻要算法裡沒有循環和遞歸，就算有上萬行代碼，時間複雜度也是
O(1)
，因為它的執行次數不會随着任何一個變量的增大而變長，比如下面這樣
public string attack(int n)
{
int power = 100;
int speed = 65;
Console.WriteLine("力量是:", power);
Console.WriteLine("速度是:", speed);
if (power == 200)
Console.WriteLine("快來救我");
.....
return "我沒事，不用擔心";
} 2、線性階 O(n)
隻有一層循環或者遞歸等，時間複雜度就是
O(n)
，這樣消耗時間随着N變化而變化，比如下面這種
public string attack(int n)
{
for (int i = 0; i < n; i++)
{
Console.WriteLine("我沒事");
}
return "我很好";
}
public string runaway(int n)
{
while(--n>0)
Console.WriteLine("跑跑跑");
return "我跑的很快";
}
public string gameover(int n)
{
Console.WriteLine("hhh");
if (--n > 0)
{
Console.WriteLine(gameover(n));
}
return "結束";
} 3、平方階 O(n²)
就是雙重for循環，如果外層的是n，内層的是m，那麼複雜度就是O(m*n)，比如下面這種
public string attack(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
Console.WriteLine("我沒事");
}
}
return "我很好";
} 還記得上面的簡化不？這樣的，總執行次數為 n + n²，如果是多項式，取最高次項，是以這個時間複雜度也是
O(n²)
public string attack(int n)
{
for (int i = 0; i < n; i++)
{
Console.WriteLine("我沒事");
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
Console.WriteLine("我沒事");
}
}
return "我很好";
} 4、對數階 O(logN)
下面的循環就按i*2何時=N，就是2的多少次方是N，即log2^N，讀作以2為底N的對數。對數公式[1] log不了解的可以點選檢視一下，這裡不做過多講解。
int i = 1;
while (i < n)
i = i * 2; 5、線性對數階 O(nlogN)
就是for循環套while，如下nlog2^N，讀作n倍以2為底N的對數。。對數公式[1] log不了解的可以點選檢視一下，這裡不做過多講解。
for (int j = 0; j < n; j++)
{
int i = 1;
while (i < n)
i = i * 2;
} 6、更多...
其他還有一些時間複雜度的運用，下面由快到慢排列了一下：
| 複雜度 | 名稱 |
|---|---|
| 常數複雜度 |
| 對數複雜度 |
| 線性時間複雜度 |
| 線性對數複雜度 |
| 平方 |
| 立方 |
| 指數，一點資料量就卡的不行 |
| 階乘，就更慢了 |
這些時間複雜度有什麼差別呢，看張圖
随着資料量或者 n 的增大，時間複雜度也随之增加，也就是執行時間的增加，會越來越慢，越來越卡。
總的來說時間複雜度就是執行時間增長的趨勢，那麼空間複雜度就是存儲空間增長的趨勢。
空間複雜度
空間複雜度就是算法需要多少記憶體，占用了多少空間。
常用的空間複雜度有
O(1)
、
O(n)
O(n²)。
O(1) 就是算法執行臨時空間不會随着N發生變化 都算成一個常量，如下。
public string attack(int n)
{
int j = 0;
for (int i = 0; i < n; i++)
{
j = i;
j++;
}
return "我很好";
} O(n)就是一開始就開辟的記憶體，不會在改變，如下new出來了N個，但是N下面循環并沒有再開臨時變量
public string attack(int n)
{
int[] m = new int[n];
int j = 0;
for (int i = 1; i < n; i++)
{
j = i;
j++;
}
return "我很好";
} 『空間複雜度』和『時間複雜度』判斷标準差不多，主要是看開了多少個臨時變量，是否跟N有一定的線性關系。
這都是一些簡單的，如果是複雜的怎麼計算呢， 下面都計算時間複雜度為例子：
- T(n) = n + 29 一般說是O(n)因為常數項影響函數增長很小
- T(n) = n^3 + n^2 + 29 一般說為O(n3)，n3 的增長速度是遠超 n^2 的，同時 n^2 的增長速度是遠超 n 的，是以有了高次項可以忽略低次項
- T(n) = 3n^3 一般說為O(n^3)因為階數比乘數影響增長速度最顯著我們通常忽略
總結
重新梳理了一遍以後，現在寫代碼眼裡浮現的都是一堆O(1)、O(n)、O(n²)、logN，感覺要瘋了。
參考資料
1.百度百科：對數公式
2.如何了解時間複雜度和空間複雜度：https://www.cnblogs.com/magicg/p/15178750.html
3.C#算法的時間複雜度和空間複雜度：https://blog.csdn.net/q_17600689511/article/details/100189543
4.c#算法時間複雜度 面試必看：https://blog.csdn.net/weixin_44370124/article/details/119321322
| 歡迎關注訂閱微信公衆号【熊澤有話說】，更多好玩易學知識等你來取 作者：熊澤-學習中的苦與樂 公衆号：熊澤有話說 出處： https://www.cnblogs.com/xiongze520/p/15666448.html 您可以随意轉載、摘錄，但請在文章内注明作者和原文連結。 |