在写 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 还是忍不住要说一说