《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 461|回复: 2
收起左侧

[CareerCup] 移动链表元素和数组开销不一样吗》

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-9-23 20:06:49 | 显示全部楼层 |阅读模式

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

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

x

http://www.1point3acres.com/bbs/ ... &fromuid=107278

2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

原作者有句话说如果是数组那么开销会巨大,why?


wzf1943 发表于 2014-9-24 02:07:54 | 显示全部楼层
不是移动的开销,而是不断开辟新空间的开销。数组和链表在速度上的差距很小。甚至可以说没有。但是空间上,数组需要开辟连续的内存,但是链表是不需要的。
回复 支持 反对

使用道具 举报

eaglesky1990 发表于 2014-9-24 02:11:36 | 显示全部楼层
链表每次移动都是O(1)时间,但如果是数组的话你把后边一个元素移到前边需要把这之间的所有元素后移来腾地方,所以是O(n)的时间(如果要保持相对顺序的话是这样,如果无需保持,则像快排那样直接交换也可,那就是O(1))。所以数组开销会更大一些。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-19 22:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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