📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5805| 回复: 26
跳转到指定楼层
上一主题 下一主题
收起左侧

空间时间复杂度一定要越小越好么

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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


上一篇:JAVA的语法小问题
下一篇:int 数组可以接受char型的?
推荐
smzfeng 2014-8-16 06:09:45 | 只看该作者
全局:
Molten 发表于 2014-8-15 16:10
嗯嗯,其实我就刷到一个挺简单的题,Preorder, Inorder, Postorder traversal不用recursion这种的,我用s ...

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

使用道具 举报

全局:
O(1)的神解我猜测是有什么公式可以一步就出来但是你不知道。。
回复

使用道具 举报

推荐
ilovetennis 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)),这个倒是个蛮有用的技巧。
回复

使用道具 举报

🔗
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遍历原来是公式么。。。。
回复

使用道具 举报

全局:
Molten 发表于 2014-8-16 05:10
那个morris遍历原来是公式么。。。。

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

点评

以及看了你后面的帖子发现你说的是空间复杂度O(1)的情形,我以为你是说时间复杂度来着。。  发表于 2014-8-16 06:13
回复

使用道具 举报

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

哦哦,谢谢大神提点~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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