目錄
- 前言
- 1. 空間復雜度是個what？
- 2. 從幾個例子來理解空間復雜度的計算
- 2.1 冒泡排序的空間復雜度
- 2.2 斐波那契陣列的空間復雜度
- 2.3 階乘的空間復雜度
- 后記
前言
hello，大家好，這篇文章用來介紹空間復雜度的一些相關知識，希望對大家有所幫助，也歡迎大家批評指正，之前博主已經寫過一篇介紹復雜度的文章了，主要是對時間復雜度的介紹，大家在閱讀本文之前也可以先閱讀一下這篇文章資料結構——優雅的復雜度，
1. 空間復雜度是個what？
空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用了多少bytes的空間，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法，
2. 從幾個例子來理解空間復雜度的計算
2.1 冒泡排序的空間復雜度
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;
}
}
在這個冒泡排序中，是接受了一個傳遞過來的陣列的，我們在計算這個演算法的空間復雜度的時候，是不考慮輸入陣列的，只考慮演算法在運行中額外搞出來的空間，
接下來我們定義了size_t 的end，int change 和size_t i，我們注意，雖然每一次回圈進入，i的值會改變，但是i的空間還在那里，沒有重新定義，我們要知道，時間是累計的，不可復用，而空間是不累計的，可以復用，
所以，在冒泡排序中變數的個數是3，為常數，則空間復雜度為O（1），
2.2 斐波那契陣列的空間復雜度
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibArray =
(long long *)malloc((n+1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;for (int i = 2; i <= n ; ++i)
{
fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2];
}
return fibArray ;
}
在這個演算法中，假設我們要求0~n的的斐波那契陣列，我們是需要開出具有n個空間的，空間復雜度為O(N)，雖然這個演算法求的不是斐波那契陣列，但是在它運行的程序中，是開辟了斐波那契陣列的空間的，也就是說，在運行程序中，是開辟出了n個變數空間的，雖然還定義了i等變數，但根據大O的漸進表示法，斐波那契數列的空間復雜度為O(N)，
2.3 階乘的空間復雜度
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
遞回演算法的空間復雜度通常是遞回的層數，在階乘中，每一次呼叫都會建立堆疊幀，堆疊幀里面存盤引數和區域變數，所以在執行程序中，是建立了n個堆疊幀的，而每一次呼叫堆疊幀的程序中，又會使用常數個空間，根據大O的漸進表示法，空間復雜度為O(N)，
后記
好的，關于空間復雜度我們就先分享到這里了，希望對大家有所幫助，我們下期文章再見，感謝大家多多支持，你們的支持是博主進步的動力，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299182.html
標籤：其他