一亩三分地论坛

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

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

[算法题] 空间时间复杂度一定要越小越好么

[复制链接] |试试Instant~ |关注本帖
Molten 发表于 2014-8-16 02:38:22 | 显示全部楼层 |阅读模式

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

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

x
最近刷题刷得好崩溃,特别是看到网上各种O(1) complexity的神解更是无语了。。。比较纠结的是不是leetcode上能过的代码空间时间就算合格了,不需要一定去纠结超低的复杂度吧?感觉那样纠结下去刷题很慢而且学习曲线陡峭难以坚持啊。。。

tsl665 发表于 2014-8-16 04:54:15 | 显示全部楼层
O(1)的神解我猜测是有什么公式可以一步就出来但是你不知道。。
回复 支持 1 反对 0

使用道具 举报

smzfeng 发表于 2014-8-16 06:09:45 | 显示全部楼层
Molten 发表于 2014-8-15 16:10
嗯嗯,其实我就刷到一个挺简单的题,Preorder, Inorder, Postorder traversal不用recursion这种的,我用s ...

这是一个方面 但是在面试时候应该重点不在变量名和注释上
重点是 你写的代码在逻辑正确的前提下让人好懂 这个就比较潜移默化了 多看一些别人的代码 就会有感觉的
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2014-8-16 03:10:07 | 显示全部楼层
O 1??
这。。。。很少有题时间能到1吧
回复 支持 反对

使用道具 举报

smzfeng 发表于 2014-8-16 04:48:33 | 显示全部楼层
我觉得除了追求复杂度以外,还要注意代码的可维护性。你提到的O(1)的题,应该很少见到,如果见到了,应该就是为了考察你O(1)的那种解法的,所以不能忽视。另外,往往时间和空间的复杂度一个降低了,另一个就会升高。
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-16 05:07:20 | 显示全部楼层
readman 发表于 2014-8-16 03:10
O 1??
这。。。。很少有题时间能到1吧

是挺少的啦,只是拒个极端例子来说明我的情况而已。。。。
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-16 05:10:10 | 显示全部楼层
本帖最后由 Molten 于 2014-8-16 05:18 编辑
smzfeng 发表于 2014-8-16 04:48
我觉得除了追求复杂度以外,还要注意代码的可维护性。你提到的O(1)的题,应该很少见到,如果见到了,应该 ...

嗯嗯,其实我就刷到一个挺简单的题,Preorder, Inorder, Postorder traversal不用recursion这种的,我用stack做出来了是time:O(n), space:O(n).一去网上搜居然有大神用什么Morris遍历做出来time:O(n), space:O(1)。。。一看就吓尿了。。。

对啦,大神你提到了代码的可维护性是说要多comment,variable选make sense的么?
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-16 05:10:35 | 显示全部楼层
tsl665 发表于 2014-8-16 04:54
O(1)的神解我猜测是有什么公式可以一步就出来但是你不知道。。

那个morris遍历原来是公式么。。。。
回复 支持 反对

使用道具 举报

tsl665 发表于 2014-8-16 06:12:11 | 显示全部楼层
Molten 发表于 2014-8-16 05:10
那个morris遍历原来是公式么。。。。

哦这倒不是,我只是看到了这个帖子想到以前遇到过类似的情形就是有一个公式一步就出来了。。
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-16 11:48:25 | 显示全部楼层
smzfeng 发表于 2014-8-16 06:09
这是一个方面 但是在面试时候应该重点不在变量名和注释上
重点是 你写的代码在逻辑正确的前提下让人好懂 ...

哦哦,谢谢大神提点~
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-16 11:48:58 | 显示全部楼层
tsl665 发表于 2014-8-16 06:12
哦这倒不是,我只是看到了这个帖子想到以前遇到过类似的情形就是有一个公式一步就出来了。。

哦哦,好吧,大神果然是数学大牛啊。。。
回复 支持 反对

使用道具 举报

eaglesky1990 发表于 2014-8-16 22:27:15 | 显示全部楼层
Molten 发表于 2014-8-16 05:10
嗯嗯,其实我就刷到一个挺简单的题,Preorder, Inorder, Postorder traversal不用recursion这种的,我用s ...

哦你说的O(1)指的是空间复杂度吧。。从我目前刷题的情况来看,在时间复杂度相同的前提下,空间复杂度自然是越低越好啦。。不过我觉得那些空间复杂度相对较低的算法,有些确实想出来比较有难度,尤其是在面试的时间压力下。。所以我个人觉得那些太tricky的可以先放一放,不知各位经验人士如何看。。

另外这个Morris遍历之所以能做到将空间复杂度降到O(1), 本质上是利用了原来结点中没有用到的空间(which is O(n)),这个倒是个蛮有用的技巧。
回复 支持 反对

使用道具 举报

eaglesky1990 发表于 2014-8-16 22:27:30 | 显示全部楼层
Molten 发表于 2014-8-16 05:10
嗯嗯,其实我就刷到一个挺简单的题,Preorder, Inorder, Postorder traversal不用recursion这种的,我用s ...

哦你说的O(1)指的是空间复杂度吧。。从我目前刷题的情况来看,在时间复杂度相同的前提下,空间复杂度自然是越低越好啦。。不过我觉得那些空间复杂度相对较低的算法,有些确实想出来比较有难度,尤其是在面试的时间压力下。。所以我个人觉得那些太tricky的可以先放一放,不知各位经验人士如何看。。

另外这个Morris遍历之所以能做到将空间复杂度降到O(1), 本质上是利用了原来结点中没有用到的空间(which is O(n)),这个倒是个蛮有用的技巧。
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-8-17 00:59:01 | 显示全部楼层
我觉得面试的时候可以先focus在算法的正确性上,然后再去优化时间和空间复杂度,没必要太纠结
Premature optimization is the root of all evil
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-17 01:16:58 | 显示全部楼层
grassgigi 发表于 2014-8-17 00:59
我觉得面试的时候可以先focus在算法的正确性上,然后再去优化时间和空间复杂度,没必要太纠结
Premature o ...

嗯嗯,有道理~我现在就是直接一路刷过去了,准备第二遍再去纠结complexity的问题。。。
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-17 01:17:34 | 显示全部楼层
eaglesky1990 发表于 2014-8-16 22:27
哦你说的O(1)指的是空间复杂度吧。。从我目前刷题的情况来看,在时间复杂度相同的前提下,空间复杂度自然 ...

嗯嗯~谢谢大神点拨~
回复 支持 反对

使用道具 举报

dzf1992 发表于 2014-8-21 18:55:16 | 显示全部楼层
为了追求效率有时会带来编码难度、可读性,可维护性增加。若效率并没有成为木桶中的短板,那么我觉得没有暂时没有必要过度优化哈。
回复 支持 反对

使用道具 举报

wzf1943 发表于 2014-8-21 23:41:23 | 显示全部楼层
某公司的面试官的原话,面试的时候,他们首先看重的是你代码的逻辑是不是清晰。其次你的时间复杂度要差不多说得过去,至于最优解还得看缘分和你当时的状态。多少情况下,你的code差不多的情况下,不会因此拒绝你,倒是会和你讨论一下优化之类的事情。
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-22 04:58:31 | 显示全部楼层
dzf1992 发表于 2014-8-21 18:55
为了追求效率有时会带来编码难度、可读性,可维护性增加。若效率并没有成为木桶中的短板,那么我觉得没有暂 ...

嗯嗯,很有道理,谢谢大神解惑~
回复 支持 反对

使用道具 举报

 楼主| Molten 发表于 2014-8-22 04:59:26 | 显示全部楼层
wzf1943 发表于 2014-8-21 23:41
某公司的面试官的原话,面试的时候,他们首先看重的是你代码的逻辑是不是清晰。其次你的时间复杂度要差不多 ...

嗯嗯,谢谢大神解惑~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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