一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 448|回复: 4
收起左侧

[算法题] 关于递归与空间复杂度

[复制链接] |试试Instant~ |关注本帖
dae 发表于 2015-7-17 00:28:27 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一般递归会算进空间复杂度吗?
例如:
public int zero1(int n) {
    while (n > 0) {
        n--;
    }
    return 0;
}
zero1 的空间复杂度是 O(1)

但是。。
public int zero2(int n) {
    if (n <= 0) return 0;
    return zero(n - 1);
}
zero2 的空间复杂度是 O(n) 还是 O(1) ?



stellari 发表于 2015-7-17 13:42:43 | 显示全部楼层
(额外)空间复杂度是在程序中除了输入输出以外所需要用的内存空间大小,无论这个内存如何分配,分配到哪里,不应该影响空间复杂度的取值。所以,递归的空间复杂度至少是O(递归深度)。否则,如果zero2的空间复杂度是O(1),那么很多其他算法:比如二叉树普通先序遍历和快排等的空间复杂度也都是O(1)了。这个逻辑就好比说,因为我们“看不见这个内存分配的过程,所以这个内存分配不存在”。至少我认为这个逻辑是不能接受的。

当然,或许你的面试官会有不同意见,所以你可以说:“The program takes O(N) space on the call stack. So if that counts, the space complexity should be ... ”。这样既不会给出错误答案,又表示你确实知道这个内存分配发生在什么地方。

不过,像zero2这种尾递归,有可能编译器能够自动识别并优化成zero1的形式(比如gcc可以,Java我就不太清楚)。这点如果你了解的话也可以跟面试官提。
回复 支持 2 反对 0

使用道具 举报

wzf1943 发表于 2015-7-17 00:53:24 | 显示全部楼层
space complexity 主要是指的是在内存上额外开辟的空间,比如DP的一维二维数组。 recursive call因为是系统自行去分配和释放内存,这个过程一般面试不太会问,问起了因为这是一个动态的过程所以你也不好回答。如果真的遇见了要问recursive的空间复杂度,你自己在白板上画一下递归树好了。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

readman 发表于 2015-7-17 14:21:33 | 显示全部楼层
stellari 发表于 2015-7-17 13:42
(额外)空间复杂度是在程序中除了输入输出以外所需要用的内存空间大小,无论这个内存如何分配,分配到哪里 ...

tail call么? 听说8有, 具体就没听过有人说怎么优化了, 这种优化局限性很大....
回复 支持 反对

使用道具 举报

celestial 发表于 2015-7-17 14:50:32 | 显示全部楼层
每一次调用函数,形参就需要开辟存储空间,所以回答O(n)比较靠谱
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表