问一个时间复杂度的问题，求教求教 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个时间复杂度的问题，求教求教

问一个时间复杂度的问题，求教求教# JobHunting - 待字闺中

d*k2014-05-31 07:05

1 楼

之前我计算时间复杂度都只是考虑到算法本需要的时间
比如说我在实现中用一个ArrayList来存东西，我就默认ArrayList的存取都为恒定值
然后昨天被面试官质疑了
说我用ArrayList的insertion是O(n)的操作，所以实际的time complexity比我估计的
大很多
我想问一下这种情况多见么？
那我岂不是还要熟悉某个特定语言中数据结构的怎么实现的？

s*x2014-05-31 07:05

2 楼

这个是基本要求阿。you donot need to the details, you have to have a sense
for some basic calls, for examples, most of the common containers.
There is no magic, you should look it up when in doubt.

l*b2014-05-31 07:05

3 楼

不用担心，不懂的永远用不到。常用到的肯定都会。
写java了还关心什么数据结构，不差那点效率

【在 d**k 的大作中提到】

: 之前我计算时间复杂度都只是考虑到算法本需要的时间
: 比如说我在实现中用一个ArrayList来存东西，我就默认ArrayList的存取都为恒定值
: 然后昨天被面试官质疑了
: 说我用ArrayList的insertion是O(n)的操作，所以实际的time complexity比我估计的
: 大很多
: 我想问一下这种情况多见么？
: 那我岂不是还要熟悉某个特定语言中数据结构的怎么实现的？

d*k2014-05-31 07:05

4 楼

问题是他考阿
我算法平时都不用的

【在 l*******b 的大作中提到】

: 不用担心，不懂的永远用不到。常用到的肯定都会。
: 写java了还关心什么数据结构，不差那点效率

d*k2014-05-31 07:05

5 楼

谢谢
那我再补补课

【在 s**x 的大作中提到】

: 这个是基本要求阿。you donot need to the details, you have to have a sense
: for some basic calls, for examples, most of the common containers.
: There is no magic, you should look it up when in doubt.

z*e2014-05-31 07:05

6 楼

arraylist复杂度是o(n)那是最糟糕的情况
这个考官也是不懂
arraylist的insert明明是o(1) amortized
因为list本身有长度，如果超过了，需要扩充内存
但是平均起来是个常量
这个题目也不少太少见，见过几次

d*k2014-05-31 07:05

7 楼

谢谢
不知道JAVA具体怎么实现的

【在 z****e 的大作中提到】

: arraylist复杂度是o(n)那是最糟糕的情况
: 这个考官也是不懂
: arraylist的insert明明是o(1) amortized
: 因为list本身有长度，如果超过了，需要扩充内存
: 但是平均起来是个常量
: 这个题目也不少太少见，见过几次

z*e2014-05-31 07:05

8 楼

你是不是用了很多arraylist.add(0,object)？
单纯的add(object)就是o(1) amortized

d*k2014-05-31 07:05

9 楼

我就是用了add 而已
他问我ArrayList的add是什么时间的
我张口就,常数阿
他表示很质疑

【在 z****e 的大作中提到】

: 你是不是用了很多arraylist.add(0,object)？
: 单纯的add(object)就是o(1) amortized

z*e2014-05-31 07:05

10 楼

那这个面官真够烂的，你说常数是对的
就是这个常数复杂度里面有点文章可以做就是了
http://stackoverflow.com/questions/5846183/arraylist-vs-linkedl

【在 d**k 的大作中提到】

: 我就是用了add 而已
: 他问我ArrayList的add是什么时间的
: 我张口就,常数阿
: 他表示很质疑

l*b2014-05-31 07:05

11 楼

要理解面试官也是背了几页培训资料装门面，结果还背错了 :)

【在 z****e 的大作中提到】

: 那这个面官真够烂的，你说常数是对的
: 就是这个常数复杂度里面有点文章可以做就是了
: http://stackoverflow.com/questions/5846183/arraylist-vs-linkedl

l*a2014-05-31 07:05

12 楼

你是说古路旁的面试观烂？

【在 z****e 的大作中提到】

: 那这个面官真够烂的，你说常数是对的
: 就是这个常数复杂度里面有点文章可以做就是了
: http://stackoverflow.com/questions/5846183/arraylist-vs-linkedl

z*e2014-05-31 07:05

13 楼

那你说，楼主妹子说arraylist的复杂度说错了吗？

【在 l*****a 的大作中提到】

: 你是说古路旁的面试观烂？

q*c2014-05-31 07:05

14 楼

虽然没错，但是是胡乱蒙的，所以别人一追问就露怯了。。。

【在 z****e 的大作中提到】

: 那你说，楼主妹子说arraylist的复杂度说错了吗？

z*e2014-05-31 07:05

15 楼

比起说成是o(n)的面官，我觉得这个蒙的直觉还更靠谱
arraylist被蒙成array基本上对
但是如果想成是linkedlist，那就是个错误了

【在 q*c 的大作中提到】

: 虽然没错，但是是胡乱蒙的，所以别人一追问就露怯了。。。

a*m2014-05-31 07:05

16 楼

ArrayList的存取是O(n)吧。俺怎么觉得面试官没说错。append可以勉强算o(1)，但是
lz明明说了是insert呀。

a*m2014-05-31 07:05

17 楼

复杂度效率和overhead效率是两码事。复杂度效率当然需要知道。

【在 l*******b 的大作中提到】

: 不用担心，不懂的永远用不到。常用到的肯定都会。
: 写java了还关心什么数据结构，不差那点效率

P*r2014-05-31 07:05

18 楼

ArrayList 的 Insert 是 O(n)吧。 add 才是O(1)。
不然还要什么hashlinkedlist干嘛

d*k2014-05-31 07:05

19 楼

用的是add

【在 P******r 的大作中提到】

: ArrayList 的 Insert 是 O(n)吧。 add 才是O(1)。
: 不然还要什么hashlinkedlist干嘛

d*k2014-05-31 07:05

20 楼

那我们一般分析时间效率要不要考虑overhead效率？
还是就算复杂度效率就可以了？

【在 a********m 的大作中提到】

: 复杂度效率和overhead效率是两码事。复杂度效率当然需要知道。

a*m2014-05-31 07:05

21 楼

overhead只是常数，慢点总是有限，区别是3秒还是4秒这种。算法复杂度是数量级问题
，区别是3秒还是3年的问题。big o里面常数都可以忽略。overhead一般在这部分。

【在 d**k 的大作中提到】

: 那我们一般分析时间效率要不要考虑overhead效率？
: 还是就算复杂度效率就可以了？

z*e2014-05-31 07:05

22 楼

arraylist这个类根本没有append和insert方法，只有一个add
java的list接口就只定义了add，没定义其他方法
看下面
我问楼主后的答覆
发信人: duck (五月飞花), 信区: JobHunting
标题: Re: 问一个时间复杂度的问题，求教求教
发信站: BBS 未名空间站 (Sat May 31 11:44:06 2014, 美东)
我就是用了add 而已
他问我ArrayList的add是什么时间的
我张口就,常数阿
他表示很质疑

【在 a********m 的大作中提到】

: ArrayList的存取是O(n)吧。俺怎么觉得面试官没说错。append可以勉强算o(1)，但是
: lz明明说了是insert呀。

z*e2014-05-31 07:05

23 楼

java的list有定义过insert这个方法么？
http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.ht

【在 P******r 的大作中提到】

: ArrayList 的 Insert 是 O(n)吧。 add 才是O(1)。
: 不然还要什么hashlinkedlist干嘛

z*e2014-05-31 07:05

24 楼

ft
去哪里来的hashlinkedlist这个类
听说过linkedhashmap和linkedhashset
第一次听说hash跟list扯上关系的
你说的是linkedlist吧，这个不常用

【在 P******r 的大作中提到】

: ArrayList 的 Insert 是 O(n)吧。 add 才是O(1)。
: 不然还要什么hashlinkedlist干嘛