---
tags: 演算法, LeetCode
disqus: HackMD
---
# 時間複雜度 與 空間複雜度
同一個演算法在不同等級的電腦上跑，效率可能會有所不同，我們可以透過比較科學的方式，就是計算時間複雜度`(Time Complexity)`與空間複雜度`(Space Complexity)`來判斷演算法好壞。
## 時間複雜度
> 衡量程式執行的速度
### 介紹
時間複雜度可以使用`Big O Notation`來展示複雜度的趨勢，`Big-Ο`代表演算法時間函式的上限`(Upper bound)`，而在最壞的狀況下，演算法的執行時間不會超過`Big-Ο`。
那該如何計算`Big O Notation`，有三個規則:
* 常數可忽略不計
* 取最大次方
* Log底數可忽略不計
假設我們要求`f(n) = 3n+2`這段方程式的時間複雜度，根據上面所述規則，將常數部分去掉，根據[漸進分析](https://en.wikipedia.org/wiki/Asymptotic_analysis)，在`n`變得非常大時，常數部分就變得微不足道，於是取得時間複雜度為`O(n)`。
以下為常見時間複雜度，接下來會一一舉例。
| Big O Notation | 別名 | 常見演算法 |
| -------- | -------- | -------- |
| [$O(1)$](#O1-Constant-time) | 常數 | 陣列讀取 |
| [$O(n)$](#On-Linear-time) | 線性 | [Linear search](https://en.wikipedia.org/wiki/Linear_search)|
| [$O(logn)$](#Olog-n-Logarithmic-time) | 對數(Logarithmic ) | [二分搜尋法](https://en.wikipedia.org/wiki/Binary_search_algorithm)|
| $O(nlogn)$ | 線性 | [堆積排序](https://hackmd.io/@SupportCoding/Heap_sort)，[合併排序](/Merge_sort) |
| $O(n^2)$ | 平方 | [氣泡排序](https://en.wikipedia.org/wiki/Bubble_sort)，[插入排序](https://en.wikipedia.org/wiki/Insertion_sort)|
| [$O(n^3)$](#On3-Cubic-time) | 三次方 | 三重迴圈枚舉法，高斯消去法求解線性方程組 |
| $O(2^n)$ | 指數 | 費氏數列 |
| [$O(n!)$](#On-Factorial-time) | 階層 | 排列組合，八皇后問題 |
### O(1): Constant time
不管帶入的 `n` 多大，執行時間不會隨著 `n` 變大而增加，固為 $O(1)$。
```javascript=
/**
* @param {number} n The number
*/
function printNum(n){
console.log(n);
}
printNum(10);
```
### O(n): Linear time
隨著輸入的增長，算法的完成時間會相應增加，取最大階項`n`，固為$O(n)$。
```javascript=
/**
* @param {number} n The number
*/
function forloop(n){
for(i=0;i<n;i++){
console.log(i);
}
}
forloop(10);
```
### O(log n): Logarithmic time
```javascript=
/**
* @param {number} n The number
*/
function Logarithmic(n){
let i = 1;
while(i < n){
i = i * 2;
}
}
Logarithmic(8);
```
可以發現`i`會是$$2^0, 2^1 ,2^2, 2^3, 2^4, ... 2^n$$結果與自身反覆相乘，就表明正使用對數算法，能夠對半$（n/2）$處理的通常都屬於 $O(log n)$ 的演算法
假設 `n` 是 `8`，迴圈總共會跑 `3` 次，$n = 2^3$也就是 $\log2^n = 3$ ，將底數忽略，時間複雜度為$O(\log n)$
$O(log n)$基本上意味著時間呈線性增長，而`n`呈指數增長。因此，如果計算`2`元素需要一秒鐘，計算`4`元素則需要`2`幾秒鐘，計算`8`元素需要幾3秒鐘，依此類推等等。
### O(n^3): Cubic time
此函式接受兩個陣列 `A` 和 `B`，並傳回它們相乘的結果。它使用三個巢狀迴圈，最外層回圈遍歷第一個陣列的列，中間層的迴圈遍歷第二個陣列的行，最內層陣列遍歷相應行和列的元素。
以下程式只是個範例，有更有效的演算法來執行矩陣乘法，例如:[施特拉森演算法(Strassen)算法](https://zh.wikipedia.org/zh-tw/%E6%96%BD%E7%89%B9%E6%8B%89%E6%A3%AE%E6%BC%94%E7%AE%97%E6%B3%95))。
```javascript=
function matrixMultiplication(A, B) {
let result = new Array(A.length).fill(0).map(() => new Array(B[0].length).fill(0));
for (let i = 0; i < A.length; i++) {
for (let j = 0; j < B[0].length; j++) {
for (let k = 0; k < A[0].length; k++) {
result[i][j] += A[i][k] * B[k][j];
}
}
}
return result;
}
```
### O(2^n): Exponential time
使用循環遍歷輸入陣列的元素，對於每個元素，它透過將元素添加到每個現有子集來建立一個新子集。每添加一個元素，子集的數量就會加倍。此函式的時間複雜度為 $O(2^n)$，因為它會產生 $2^n$ 個子集，其中 $n$ 是輸入陣列的大小。
```javascript=
function generateSubsets(set) {
let subsets = [[]];
for (let i = 0; i < set.length; i++) {
let current = set[i];
let n = subsets.length;
for (let j = 0; j < n; j++) {
let subset = subsets[j].slice();
subset.push(current);
subsets.push(subset);
}
}
return subsets;
}
generateSubsets([1, 5]) // [[], [1], [5], [1, 5]]
```
#### 位元操作Bit manipulation改進
時間複雜度保持不變，但通過減少迭代次數和操作次數提高了性能。
```javascript=
function generateSubsetsUsingBitManipulation(set) {
let n = set.length;
let subsets = [];
for (let i = 0; i < (1 << n); i++) {
let subset = [];
for (let j = 0; j < n; j++) {
if (i & (1 << j)) {
subset.push(set[j]);
}
}
subsets.push(subset);
}
return subsets;
}
generateSubsetsUsingBitManipulation([1, 5]) // [[], [1], [5], [1, 5]]
```
### O(n!): Factorial time
這個函式只要產生了所有的 `n` 階層的排列，其中 `n` 是輸入陣列的大小。重要的是要注意這只是一個示例，在實際情況下，有更有效的演算法來生成排列，比如 `Heap` 演算法。
```javascript=
function generatePermutations(arr) {
let result = [];
function permute(arr, m = []) {
if (arr.length === 0) {
result.push(m);
} else {
for (let i = 0; i < arr.length; i++) {
let curr = arr.slice();
let next = curr.splice(i, 1);
permute(curr.slice(), m.concat(next))
}
}
}
permute(arr);
return result;
}
generatePermutations([1,2]) // [[1, 2], [2, 1]]
```
#### 使用Heap演算法改進
使用了`Heap`的演算法來產生所有的排列，相比於上一個是一種更加高效的方法。它使用遞迴函式，在每次遞迴呼叫中，它產生前 `n-1` 個元素的所有排列，並將最後一個元素與陣列中的前 `n-1` 個元素交換。它不在每個遞迴呼叫中使用切片`slice`或連接`concat`，這就是它比前一個更有效的原因。
```javascript=
function generatePermutationsUsingHeapsAlgorithm(arr) {
let result = [];
function permute(arr, n) {
if (n === 1) {
result.push(arr.slice());
} else {
for (let i = 0; i < n; i++) {
permute(arr, n - 1);
if (n % 2 === 0) {
swap(arr, i, n - 1);
} else {
swap(arr, 0, n - 1);
}
}
}
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
permute(arr, arr.length);
return result;
}
generatePermutationsUsingHeapsAlgorithm([1,2]) // [[1, 2], [2, 1]]
```
## 空間複雜度
> 程式執行所需的記憶體空間
### 介紹
時間複雜度與空間複雜度是互相
也就是**以時間換取空間，以空間換取時間**
以下為常見空間複雜度
| Big O Notation | 介紹 | 常見 |
| -------------- | -------------------------------------------- | ---------------------------- |
| [$O(1)$](#O1-空間複雜度) | 不隨輸入資料量增加而增加 | 常數空間的演算法 |
| [$O(n)$](#span-idMathJax-Element-40-Frame-classmjx-chtml-MathJax_CHTML-tabindex0-stylefont-size-113-position-relative-data-mathmlOn-rolepresentationOnOnOn-空間複雜度) | 記憶體空間和輸入資料量等同 | 需要儲存輸入資料的演算法 |
| [$O(n^2)$](#On2-空間複雜度) | 記憶體空間是輸入資料量的平方 | 需要儲存兩兩之間關係的演算法 |
| [$O(log n)$](#Olog-n空間複雜度) | 記憶體空間輸入資料量之間呈對數關係 | 遞迴演算法 |
| $O(n log n)$ | 記憶體空間是輸入資料量乘以`log`(輸入資料量) | # |
| [$O(n + k)$](#On--k空間複雜度) | # | 基數排序 |
| $O(2^n)$ | 記憶體空間是 `2` 的輸入資料量次方 | # |
### $O(1)$ 空間複雜度
函式僅使用恆定數量的記憶體來儲存 `sum` 變數，而不管 `a` 和 `b` 的輸入值如何。因此，這個函式的空間複雜度是$O(1)$。
```javascript=
function addNum(a, b) {
let sum = a + b
return sum;
}
addNum(4, 5) // 9
```
### $O(n)$ 空間複雜度
範例為反轉陣列，儲存反轉陣列的大小與輸入陣列的大小成正比。因此，這個函數的空間複雜度是$O(n)$。
```javascript=
function reverseArray(arr) {
let reversedArr = [];
for (let i = arr.length - 1; i >= 0; i--) {
reversedArr.push(arr[i]);
}
return reversedArr;
}
reverseArray([5,8,7,9,10]) // [10, 9, 7, 8, 5]
```
### $O(n^2)$ 空間複雜度
該函數使用一個陣列來儲存輸入陣列中所有可能的元素對。對數為 $n(n-1)/2$ 個，其中 `n` 是輸入陣列的大小。因此，這個函數的空間複雜度是$O(n^2)$。
```javascript=
function generatePairs(arr) {
let pairs = [];
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i !== j) {
pairs.push([arr[i], arr[j]]);
}
}
}
return pairs;
}
generatePairs([1,3]) // [[1, 3], [3, 1]]
```
### $O(log n)$空間複雜度
該函數使用遞迴對輸入陣列執行二分搜尋法。
該函數僅使用少量記憶體來儲存高低指標(high, low)和中間變數(mid)，以及遞迴的呼叫的`stack`。 由於 `stack` 的大小與輸入陣列大小的對數成正比，因此該函數的空間複雜度為 $O(log n)$。
```javascript=
function binarySearch(arr, target) {
function search(low, high) {
if (low > high) {
return -1;
}
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
return search(mid + 1, high);
} else {
return search(low, mid - 1);
}
}
return search(0, arr.length - 1);
}
```
### $O(n + k)$空間複雜度
基數排序的空間複雜度通常為 $O(n + k)$，其中 `n` 是輸入陣列中元素的數量，`k` 是可能的數字或位數。這是因為基數排序使用輔助資料結構（例如計數陣列或`buckets`）在對元素進行排序時臨時儲存元素。
```javascript=
function radixSort(arr) {
let max = Math.max(...arr);
let maxDigits = (max + '').length;
for (let i = 0; i < maxDigits; i++) {
let buckets = Array.from({length: 10}, () => []);
for (let j = 0; j < arr.length; j++) {
let digit = getDigit(arr[j], i);
buckets[digit].push(arr[j]);
}
arr = [].concat(...buckets);
}
return arr;
}
function getDigit(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}
radixSort([5,4,8,9,10]) // [4, 5, 8, 9, 10]
```
## 特別感謝
感謝[Howard Gou](https://hackmd.io/@toto6038)大大訂正
Sign in with Wallet
Connect another wallet