l*****e
发帖数: 1374 | |
c********1
发帖数: 161 | 2 当然不是，比如quick sort就是可以用递归实现的in place sorting....... In place
的意义不在于不用空间或者用的空间很小，而是说随着N的增长，运行所需的extra的空
间是constant的。 |
l*****e
发帖数: 1374 | |
f****4
发帖数: 1359 | 4 递归函数的space怎么算？
如果递归函数本地有个变量，递归函数被调用k次，space算k还是算1？
递归函数本身的堆栈空间忽略不计么？
递归函数，书上就速度分析，没有空间分析（也可能我看漏了）
place
【在 c********1 的大作中提到】
: 当然不是，比如quick sort就是可以用递归实现的in place sorting....... In place
: 的意义不在于不用空间或者用的空间很小，而是说随着N的增长，运行所需的extra的空
: 间是constant的。
|
a********m
发帖数: 15480 | |
c********1
发帖数: 161 | 6 这个问题就难说了，不是一句两句说得清的，可以自己体会下merge sort和quick sort
的算法空间复杂度。另外，递归往深了说就是stack，既然自己外部调用stack可以做到
inplace和计算空间复杂度，那么递归用program stack也就可以用同样的方法计算了。 |
f****4
发帖数: 1359 | 7 这里就用树的中续遍历来说好了
如果是用stack的话，stack最长要能存储树的最长路径
最坏情况长度为n，最优为lgn
那么用递归的话，如果空间需要考虑stack的话，递归算不算inplace？
如果我们认为递归的stack开销不考虑，那么，我假设在这个树递归函数里面maintain
了一个local变量
那么因为这个函数在单核情况下，同一时间最多被调用n次，最少lgn次。那么这个算法
算是inplace么？（毕竟这里用到的额外内存为lgn ~ n 个）
还有，书上那个stack的分析是Amortized analysis
难道inplace也可以说是Amortized inplace?
sort
【在 c********1 的大作中提到】
: 这个问题就难说了，不是一句两句说得清的，可以自己体会下merge sort和quick sort
: 的算法空间复杂度。另外，递归往深了说就是stack，既然自己外部调用stack可以做到
: inplace和计算空间复杂度，那么递归用program stack也就可以用同样的方法计算了。
|
