在寫 LeetCode 題目的時候，很多人會去討論一個解法的時間與空間複雜度
不過有蠻多細節可以討論的
1. Stack 的空間複雜度
有不少人會犯的一個錯是沒考慮到 stack 所占的空間
多半是在用遞迴實作 DFS 時會發生
很多人就直接把 local variable 當作是 constant space 了
沒有想到如果遞迴深度是 L 的話，其實會有 L 份 local variable
今天每日一題的最高票回答就是一個例子，底下也有很多人更正他
不過有個例外是 tail recursion 的優化
例如以下這個例子:
int fact(int value, int ret = 1) {
if (value == 1)
return ret;
return fact(value - 1, ret * value);
}
這個函數會計算階乘，例如要計算 fact(5) 時，會是
fact(5, ret=1)
fact(4, ret=5)
fact(3, ret=20)
fact(2, ret=60)
fact(1, ret=120)
答案就會是 5 * 4 * 3 * 2 * 1。
如果沒有進行 tail recursion 的優化的話
執行 fact(N) 會有 N 份 value 和 N 份 ret，需要花 O(N) 空間
但可以發現，當我要呼叫 fact(value - 1, ret * value) 時
拿到回傳的結果我就直接再回傳回去了
所以跳到下一層之後原本的 value 和 ret 就已經沒用了
其實可以把當下的 value 和 ret 改成 value - 1 和 ret * value
然後重跑一遍這個函式，會是一樣的結果
這種情況下空間就只需要 O(1)，而不是 O(N)
2. 修改輸入的空間複雜度
同樣也是今天的例子，比起另開一個 visited[][] 來表示走過的位置
有些人會選擇把 board[x][y] 標記成 '*' 這個並非大小寫字母的值來表示已經走過
並宣稱這是 "no extra space"
其實我覺得這蠻白癡的，今天是剛好他的 constraint 是只有大小寫字母
如果他改成是整個 char 的範圍，你不就存不下了
他也不是在題敘裡說一定是大小寫字母，而是在 constraint 裡說的
那你怎麼不說你所有在 LeetCode 的演算法時間複雜度是 O(1)
因為題目的 N 都會有一個常數的上限?
我的標準很簡單，寫在題目敘述裡的是常數
例如題目是 DNA，那我就認同 4 種鹼基的 4 是一個常數
但如果是寫在 constaint 裡的，就是可以變化的值
當然以現實角度而言，一切都是 concrete，有個實際的值
寫題目的時候大家也是在算類似 26 * 1000 * 1000 會不會太大之類的
所以有時候看到 O(26N) 這種看起來很詭異的表示法我反而覺得他很懂
3. index 的空間複雜度
如果想的很仔細的話，可能會發現剛才的標準要嚴格的執行的話會有麻煩
例如，給定一個陣列，要求回傳有最大值的 index，請問空間複雜度?
大部分的人都會說 O(1) 吧，一直維護目前最大值的 index 就可以了
但仔細想會發現，如果陣列的大小超過 2^32 你的 index 就不能用 4-byte 整數表示了
實際上，會需要花 O(logN) 的空間表示一個 index，其中 N 是陣列的大小
但沒人會這麼想，2^32 存不下，用 2^64 存阿，超過 2^64 大小的陣列太不實際了
所以關於這點我就不太計較，要說 O(1) 我也沒差，雖然嚴格意義上不是
結論是，複雜度這種東西本來就是參考而已
也有很多複雜度比較好的演算法要在 N 非常大的時候表現才會比較好
這樣我們也不太會去用他
但就是看到有人用錯 big-O 還是忍不住要說一說