iT邦幫忙

2021 iThome 鐵人賽

DAY 4
1
Software Development

少女人妻在廚房裡想不通的演算法系列 第 4

【在廚房想30天的演算法】Day 04 來淺談一下空間複雜度

Aloha!我是中秋節沒有肉烤的少女人妻 Uerica!今年連假沒什麼跟朋友相聚的機會,還收到一堆月餅,根本在考驗意志力。半夜想偷吃月餅的時候我都會 google 鶯歌嫦娥警惕警惕自己 XD


空間複雜度 Space Complexity

空間複雜度代表的就是程式執行時所消耗的空間。不過一般在討論演算法優劣的時候,通常較著重討論時間複雜度,因現在硬體設備越來越好,一般所使用的裝置及硬體設備,所擁有的記憶體空間也越來越大,所以除非是特殊情況的演算法,不然已較少討論空間複雜度。

不過理解概念還是很有幫助的,可以依照實際情況來將兩者做調整,某些情況
可讓程式多用一些記憶體空間來省去重複運算進而加速演算法執行時間,又或者如果沒有多餘的記憶體空間可以用時,也可相反操作。

實際計算範例

下列就來說明些常見的空間複雜度算法。

O(1)
下列例子是創建 x, y 兩變數,並讓 x, y 加一,此例子無論 x, y 值多大,都不會再多消耗記憶體空間。

let x = 0;
let y = 0;
x++
y++

O(n)
下列例子中,利用迴圈方式創建 arr 內的值,故消耗的記憶體空間會隨著n值增加而變多。

let n = 10;
let arr = []

for (let i = 1 ; i <= n ; i++){
    arr[i] = i;
}

參考資料:

【演算法】排序演算法 Sorting Algorithm


明天可以開始聊聊演算法了~!大家出門還是要戴口罩勤洗手保護自己與他人喔~!


上一篇
【在廚房想30天的演算法】Day 03 那個時間複雜度會讓人生變複雜嗎?
下一篇
【在廚房想30天的演算法】Day 05 資料結構之冰箱整理術
系列文
少女人妻在廚房裡想不通的演算法30

尚未有邦友留言

立即登入留言