目錄
一、演算法的復雜度
二、時間復雜度
時間復雜度的概念
大O的漸近表示法
時間復雜度計算舉例
三、空間復雜度
空間復雜度的概念
空間復雜度的計算舉例
四、常見復雜度對比
資料結構是計算機存盤、組織資料的方式，指相互之間存在一種或多種特定關系的資料元素的集合，而所謂演算法，簡單來說就是一系列計算步驟，用來將輸入資料轉化成輸出結果，
那么如何來衡量一個演算法的好壞呢？這就要用到本節所講述的時間復雜度與空間復雜度了，
一、演算法的復雜度
回到我們的問題，如何衡量一個演算法的好壞？只是看它的運行時間嗎？顯然，同樣的演算法在不同計算能力的計算機上的運行時間截然不同，評價一個演算法需要統一的尺標，總的來說，這個尺標大體上可以分為兩個維度，即時間與空間，
時間復雜度主要衡量一個演算法的運行快慢，而空間復雜度主要衡量一個演算法運行所需要的額外空間，但由于計算機發展迅速，計算機的存盤能力已經到了較高的水平，如今已不需要再特別關注一個演算法的空間復雜度了，
二、時間復雜度
時間復雜度的概念
時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，如前文所訴，這個具體時間從理論上來說是無法衡量的，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間于其中陳述句的執行次數成正比，演算法中的基本操作的執行次數，即為演算法的時間復雜度，
例如計算下列代碼中++count執行的次數：
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; ++i)
{
++count;
}
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}經過簡單的計算即可得到F(N) = N^2 + 2*N + 10
而隨著N的增大，后面的兩項對結果的影響逐漸減小
在計算時間復雜度的程序中，并不要求計算出精確的執行次數，只要明確大概的執行次數即可，因此我們選用大O的漸進表示法描述時間復雜度，
大O的漸近表示法
大O符號是用于描述函式漸進行為的數學符號，有以下規律：
| 1、 | 用常數1取代運行時間中所有的加法常數 |
| 2、 | 在修改后的運行次數函式中，只保留最高階項 |
| 3、 | 如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階， |
使用大O的漸進表示法后，Func1的時間復雜度為：O(N^2)
在某些演算法中，時間復雜度存在多種情況
例如：在一個長度為N的陣列中查找一個資料x，可能只需要一次，也可能需要N次，實際中往往關注演算法的最壞運行情況，因此該演算法的時間復雜度為O(N)
時間復雜度計算舉例
計算BubbleSort的時間復雜度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
}該演算法中每輪比較的次數為一個等引數列，即N-1、N-2、N-3……1；因此總的執行次數最壞為N*（N-1）/2，即等引數列求和，化簡得時間復雜度為O(N^2)
計算斐波那契遞回Fib的時間復雜度
計算遞回演算法的時間復雜度：遞回次數*每次遞回呼叫次數
long long Fib(size_t N)
{
if (N < 3)
{
return 1;
}
return Fib(N - 1) + Fib(N - 2);
}
該遞回的呼叫如同一顆“二叉樹”，由于一些分支提前呼叫結束，出現了空白區域，將其中的次數設為x次，不看這塊空白區則域每一層的呼叫次數為2^n次，因此總的次數為等比數列求和，即為2^N-1，此時減去之前多加的x次，即得到2^N-1-x次，代入時間復雜度的運演算法則可知時間復雜度為O(2^N)
三、空間復雜度
空間復雜度的概念
空間復雜度也是一個數學運算式，是對一個演算法在運行程序中臨時占用存盤空間大小的量度，
空間復雜度不是程式占用了多少bytes的空間，而是統計變數的個數，空間復雜度的計算規則與時間復雜度類似，也采用大O的漸進表示法，
注意：函式運行時所需要的堆疊空間（存盤函式、區域變數、一些暫存器等）在編譯期間已經確定好了，因此空間復雜度主要通過函式在運行時候顯式申請的額外空間來確定，
空間復雜度的計算舉例
計算斐波那契遞回Fib的空間復雜度
計算遞回的空間復雜度需要看遞回的深度
long long Fib(size_t N)
{
if (N < 3)
{
return 1;
}
return Fib(N - 1) + Fib(N - 2);
}
模型圖與之前計算時間復雜度的相同，那么時間復雜度也是O(2^N)嗎？
需要注意時間的消耗是一去不返的，而空間的占用是可以回收的，因此，計算該演算法的空間復雜度，只需要統計最長支路的深度即可（其它支路在使用記憶體時會使用之前支路呼叫完成后釋放的記憶體），所以，本演算法的時間復雜度為O(N)
四、常見復雜度對比
一般演算法常見的復雜度如下：
| 112233 | O(1) | 常數階 |
| 2n+1 | O(n) | 線性階 |
| 2n^2+2n+1 | O(n^2) | 平方階 |
| log(2)n+1 | O(logn) | 對數階 |
| n+log(2)n+1 | O(nlogn) | nlogn階 |
| n^3+2n^2+2 | O(n^3) | 立方階 |
| 2^n | O(2^n) | 指數階 |
評價演算法的好壞，一般依照下面的順序（好的在前）來比較：
O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(2^n)、O(n!)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/387900.html
標籤：其他