d*******5
发帖数: 22 | 1 要求constact space可以用recursive吗？ recursive的stack空间这里到底算不算？ |
a*****s
发帖数: 1121 | |
p*****2
发帖数: 21240 | 3
可以用尾递归
【在 d*******5 的大作中提到】
: 要求constact space可以用recursive吗？ recursive的stack空间这里到底算不算？
|
C********e
发帖数: 492 | 4 也算吧，
比如inorder遍历tree，不论是用stack还是递归，其实都是logN的space复杂度
真正的O（1）space解法，需要靠morris算法来
【在 d*******5 的大作中提到】
: 要求constact space可以用recursive吗？ recursive的stack空间这里到底算不算？
|
j*********6
发帖数: 407 | 5 之前开过一篇帖子讨论递归可不可以算是不是用额外空间 因为如果递归的时间复杂度
时logN 那么即使N是1000000，最终的空间也只不过是6。如果真的没有别的不使用空间
的方法 可以和面试官讨论一下递归是否可以算作O1的空间 |
a*****a
发帖数: 46 | 6 如果递归算空间的话，怎么O(1)判断一个链表是不是palindrome? |
k*******r
发帖数: 355 | 7 把链表反转一半，从两头一起往中间走，即space o(1) |
b******g
发帖数: 3616 | |
h***k
发帖数: 161 | 9 logN 这里底数应该是2吧。。？
【在 j*********6 的大作中提到】
: 之前开过一篇帖子讨论递归可不可以算是不是用额外空间 因为如果递归的时间复杂度
: 时logN 那么即使N是1000000，最终的空间也只不过是6。如果真的没有别的不使用空间
: 的方法 可以和面试官讨论一下递归是否可以算作O1的空间
|
h***k
发帖数: 161 | 10 space 不应该是O(n)嘛？每一个node都要visite一次。。?
【在 C********e 的大作中提到】
: 也算吧，
: 比如inorder遍历tree，不论是用stack还是递归，其实都是logN的space复杂度
: 真正的O（1）space解法，需要靠morris算法来
|
s**x
发帖数: 7506 | 11 关键是面试者对这个怎么定义， 稀里糊涂的面试者还是很多的， 所以， 沟通时第一
位的。
常识是递归使用stack to store a lot of things (return address, frame pointer,
parameters etc) on each call, 所以递归显然不是 O(1) space, 除非只调用 有限
次数。 说得时候尽量浅显易懂， 如果面试者水平有限， frame pointer 之类的就不
用提了， LOL. |
C********e
发帖数: 492 | 12 这些node不需要同时都在stack里。
stack深度最多和tree高度一样。
【在 h***k 的大作中提到】
: space 不应该是O(n)嘛？每一个node都要visite一次。。?
|
C********e
发帖数: 492 | 13 肯定不行啊
这样的话lgN都是O（1）的space了么？
而且如果我这个函数输入很大很大呢？或者需要在很多地方执行呢？
【在 j*********6 的大作中提到】
: 之前开过一篇帖子讨论递归可不可以算是不是用额外空间 因为如果递归的时间复杂度
: 时logN 那么即使N是1000000，最终的空间也只不过是6。如果真的没有别的不使用空间
: 的方法 可以和面试官讨论一下递归是否可以算作O1的空间
|
