O(n)：「時間複雜度 」和「空間複雜度 」的解題技巧
在本文中，我對時間複雜度與空間複雜度進行了詳細解說，並通過實例來說明這些概念。我解釋了如何用 O 符號表示演算法的效率，並提供了多種常見複雜度類型的例子，包括 O(1)、O(n)、O(log n)、O(n^2)、O(n log n)、O(2^n) 和 O(n!)，這有助於更好地理解各類演算法的執行效率。
描述時間複雜度和空間複雜度皆用 O 表示
- 空間複雜度可以用來衡量占用多少記憶體空間
- 時間複雜度可以用來衡量需要多少時間去處理
實作演算法時若能以較低之空間複雜度/空間複雜度則為較佳解，反之。
圖片來源: 初學者學演算法｜談什麼是演算法和時間複雜度
1. 空間複雜度
- 假如永遠只使用一個變數，那空間複雜度就是 O(1)
- 假設根據輸入值就會使用到多少變數，那空間複雜度就是 O(n)
- 假設根據輸入值就會使用到多少變數，且每進入迴圈一次就跑 n 個變數，則時間複雜度為 O(n^2)
// 空間複雜度是 O(1)
function Space(n){
let a = 1
}
// 空間複雜度是 O(n)
function Space(n){
let a = []
for (let i = 0; i < n; i++) {
a.push(i);
}
}
// 空間複雜度是 O(n^2)
function Space(n){
let a=[]
for (var i = 0; i < n; i++) {
a[i] = i
for (var j = 0; j < n; j++) {
a[i][j] = j
}
}
}
2. 時間複雜度
- 假如永遠只跑一次迴圈，那時間複雜度就是 O(1)
- 假設根據輸入值就會跑多少次迴圈，那時間複雜度就是 O(n)
- 假設根據輸入值就會跑多少次迴圈，且每進入迴圈一次就跑 n 次迴圈，則時間複雜度為 O(n^2)
// 時間複雜度是 O(1)
function Time(n){
console.log('1')
}
// 時間複雜度是 O(n)
function Time(n){
for (let i = 0; i < n; i++) {
console.log('1')
}
}
// 時間複雜度是 O(n^2)
function Time(n){
for (let i = 0; i < n; i++) {
console.log('i:', i)
for (let j = 0; j < n; j++) {
console.log('j:', j)
}
}
}
3. 時間複雜度/範例演算法整理
1. O(1) : index 搜尋
- 一步到位
2. O(log n): 二元搜尋
- 階層數
3. O(n): 陣列遍歷
- 線性
4. O(n log n) : Merge Sort
- 線性 + 階層
5. O(n^2): Bubble Sort
- 線性+線性
- 超級分支
- 底數漸大
- 階層小
6. O(2^n): 費氏數列
- 定速細胞分裂
- 底數小
- 階層漸大
7. O(n!): 排列組合
- 高速細胞分裂
- 底數從大到小
- 階層漸大
資料來源:初學者學演算法｜談什麼是演算法和時間複雜度用JavaScript學習資料結構與演算法 1：演算法與大 O 符號從 js 講解時間複雜度和空間複雜度超圖解！一次搞懂演算法