求问空间复杂度

之前面试遇到一题力扣，count number of island，用了简单的DFS然后跟面试官讨论空间复杂度的问题如果我的helper function里pass了我原始的matrix，那整体空间复杂度就是 matrix大小+ recursion depth吗? 最后面试官问到如何做到constant space请问有大神能讲解一下吗?PS 我是用python

感觉时间复杂度是mn,空间复杂度会是constants如果按楼上说的把领结的1变成0，好像不需要额外的空间存啦

空间负责度是mn，因为你得走一遍mn matrix，最差的情况就是把mn全走一遍，但是你每个点只会走一次。致于constant space，是因为如果你直接在原始matrix里面改，就可以做到。比如看到1就改成0这样。

这题能用constant space？我感觉不太可能，除非是很少见的神级算法。常规的BFS，DFS和UNION FIND都不能做到constant吧？

python不了解 但是你函数传进去的不是reference吗？怎么会是 matrix大小+ recursion depth？应该就是recursion depth， 如果你是在原来的matrix上面坐修改而不是新开了一个matrix

Sorry, 忘记提到不修改原始的matrix, 所以我另用一个used matrix，constant space可能是我跟面试官沟通理解不好，先谢谢各位

If you use union find, you don’t have to copy the matrix, but you still need int[m*n] space. It’s over my head :(

肥宅快乐水 发表于 2018-5-28 05:03
空间负责度是mn，因为你得走一遍mn matrix，最差的情况就是把mn全走一遍，但是你每个点只会走一次。致于con ...

对的，这题的空间复杂度是个坑，当初我就说错了。。。

pxu 发表于 2018-5-28 05:19
感觉时间复杂度是mn,空间复杂度会是constants如果按楼上说的把领结的1变成0，好像不需要额外的空间存啦

对，我也认为是这样