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

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

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

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

🔗
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 | 只看该作者
全局:
ilovetennis 发表于 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
某公司的面试官的原话,面试的时候,他们首先看重的是你代码的逻辑是不是清晰。其次你的时间复杂度要差不多 ...

嗯嗯,谢谢大神解惑~
回复

使用道具 举报

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

本版积分规则

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