如果题目要求in-place的space，能不能用recursion？

因为考虑到recursion有stack的问题。。。

recursion的话， space complexity  和 time complexity 至少是O(n) , 是吧？

kelvinzhong 发表于 2014-1-25 17:35
recursion的话， space complexity  和 time complexity 至少是O(n) , 是吧？

递归就不能in place了吧

求个确定答案啊各位？

in-place的space我感觉就是O(1)吧
你要是用Scheme或者Haskell写尾递归的话就算in-place，其他的递归嘛，如果只是处理指针的话应该也算，比如合并俩链表，不过那种题必须是in-place的，哪能让你一个个地复制结点。

一般来讲是不行的。因为递归还是要用到系统栈，所以其实仍然不是O(1)空间复杂度。

Recursion也是nlogn的复杂度，都在堆栈里，务必不能用，否则会被面试官鄙视死