時間復雜度和空間復雜度

算法的復雜度

??算法在編寫成可執行程序后，運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
??時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。

時間復雜度

??時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。一個算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法的時間復雜度。

大O的漸進表示法

?? 大O符號（Big O notation）：是用于描述函數漸進行為的數學符號。
推導大O階方法：

1. 用常數1取代運行時間中的所有加法常數。
2. 在修改后的運行次數函數中，只保留最高階項。
3. 如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。

常見時間復雜度計算舉例

// 計算Func2的時間復雜度？
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}// 計算Func3的時間復雜度？
void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++ k){++count;}for (int k = 0; k < N ; ++ k){++count;}printf("%d\n", count);
}// 計算Func4的時間復雜度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);
}

1. 實例1基本操作執行了2N+10次，通過推導大O階方法知道，時間復雜度為 O(N)
2. 實例2基本操作執行了M+N次，有兩個未知數M和N，時間復雜度為 O(N+M)
3. 實例3基本操作執行了10次，通過推導大O階方法，時間復雜度為 O(1)

空間復雜度

??空間復雜度也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。
空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數。空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法。
注意：函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候顯式申請的額外空間來確定。

實例

// 計算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;}
}// 計算Fibonacci的空間復雜度？
// 返回斐波那契數列的前n項
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;
}// 計算階乘遞歸Fac的空間復雜度？
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}

1. 實例1使用了常數個額外空間，所以空間復雜度為 O(1)
2. 實例2動態開辟了N個空間，空間復雜度為 O(N)
3. 實例3遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間。空間復雜度為O(N)