近期有谁要找律师？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

近期有谁要找律师？

近期有谁要找律师？# EB23 - 劳工卡

l*e2013-05-24 07:05

1 楼

p*u2013-05-24 07:05

2 楼

我有靠铺律师推荐，可以便宜几百刀，请站内联系，谢谢！

c*12013-05-24 07:05

3 楼

当然不是，比如quick sort就是可以用递归实现的in place sorting....... In place
的意义不在于不用空间或者用的空间很小，而是说随着N的增长，运行所需的extra的空
间是constant的。

l*e2013-05-24 07:05

4 楼

thanks!

f*42013-05-24 07:05

5 楼

递归函数的space怎么算？
如果递归函数本地有个变量，递归函数被调用k次，space算k还是算1？
递归函数本身的堆栈空间忽略不计么？
递归函数，书上就速度分析，没有空间分析（也可能我看漏了）

place

【在 c********1 的大作中提到】

: 当然不是，比如quick sort就是可以用递归实现的in place sorting....... In place
: 的意义不在于不用空间或者用的空间很小，而是说随着N的增长，运行所需的extra的空
: 间是constant的。

a*m2013-05-24 07:05

6 楼

好像算法书都不算。不过有的面试中会问到这个。

c*12013-05-24 07:05

7 楼

这个问题就难说了，不是一句两句说得清的，可以自己体会下merge sort和quick sort
的算法空间复杂度。另外，递归往深了说就是stack，既然自己外部调用stack可以做到
inplace和计算空间复杂度，那么递归用program stack也就可以用同样的方法计算了。

f*42013-05-24 07:05

8 楼

这里就用树的中续遍历来说好了
如果是用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也就可以用同样的方法计算了。