p*u
2 楼
我有靠铺律师推荐,可以便宜几百刀,请站内联系,谢谢!
c*1
3 楼
当然不是,比如quick sort就是可以用递归实现的in place sorting....... In place
的意义不在于不用空间或者用的空间很小,而是说随着N的增长,运行所需的extra的空
间是constant的。
的意义不在于不用空间或者用的空间很小,而是说随着N的增长,运行所需的extra的空
间是constant的。
l*e
4 楼
thanks!
a*m
6 楼
好像算法书都不算。不过有的面试中会问到这个。
c*1
7 楼
这个问题就难说了,不是一句两句说得清的,可以自己体会下merge sort和quick sort
的算法空间复杂度。另外,递归往深了说就是stack,既然自己外部调用stack可以做到
inplace和计算空间复杂度,那么递归用program stack也就可以用同样的方法计算了。
的算法空间复杂度。另外,递归往深了说就是stack,既然自己外部调用stack可以做到
inplace和计算空间复杂度,那么递归用program stack也就可以用同样的方法计算了。
f*4
8 楼
这里就用树的中续遍历来说好了
如果是用stack的话,stack最长要能存储树的最长路径
最坏情况长度为n,最优为lgn
那么用递归的话,如果空间需要考虑stack的话,递归算不算inplace?
如果我们认为递归的stack开销不考虑,那么,我假设在这个树递归函数里面maintain
了一个local变量
那么因为这个函数在单核情况下,同一时间最多被调用n次,最少lgn次。那么这个算法
算是inplace么?(毕竟这里用到的额外内存为lgn ~ n 个)
还有,书上那个stack的分析是Amortized analysis
难道inplace也可以说是Amortized inplace?
sort
【在 c********1 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 这个问题就难说了,不是一句两句说得清的,可以自己体会下merge sort和quick sort
: 的算法空间复杂度。另外,递归往深了说就是stack,既然自己外部调用stack可以做到
: inplace和计算空间复杂度,那么递归用program stack也就可以用同样的方法计算了。
如果是用stack的话,stack最长要能存储树的最长路径
最坏情况长度为n,最优为lgn
那么用递归的话,如果空间需要考虑stack的话,递归算不算inplace?
如果我们认为递归的stack开销不考虑,那么,我假设在这个树递归函数里面maintain
了一个local变量
那么因为这个函数在单核情况下,同一时间最多被调用n次,最少lgn次。那么这个算法
算是inplace么?(毕竟这里用到的额外内存为lgn ~ n 个)
还有,书上那个stack的分析是Amortized analysis
难道inplace也可以说是Amortized inplace?
sort
【在 c********1 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 这个问题就难说了,不是一句两句说得清的,可以自己体会下merge sort和quick sort
: 的算法空间复杂度。另外,递归往深了说就是stack,既然自己外部调用stack可以做到
: inplace和计算空间复杂度,那么递归用program stack也就可以用同样的方法计算了。
相关阅读
催 EAD 卡议员的回复,非常困惑,求解【EB3 2015七月第9绿】原装EB3 虎口拔牙绿了!发光包子perm未批,可以暂时h1b transfer吗感觉我要放弃了【EB2 2015七月第150绿】TSC 2012.03 EB2【H1B延期期间】AP和VISA STAMP都有效,可以出美国吗?请问这个应该咋办?You must sign the attached copy of G-325A请问:TSC的XM1390,速度怎么样怎么放 Medical report in sealed envelope?怀孕了485体检RFEH4 EAD拿到后,H1能跳槽吗?公证书的顺序用EB2交485的文件中需要提及EB3的140吗2011年3月的原装EB2,今年还有可能绿吗?还是要等到明年啊?除了议员,T2还有什么办法催绿吗?【EB2 2015七月第144绿】eb2 12.4 nsc没降级 这是绿了吧有人PP 两个140的么?这是什么情况, So Strange请教下PERM和485可以同时提交么?