d**k
发帖数: 797 | 1 之前我计算时间复杂度都只是考虑到算法本需要的时间
比如说我在实现中用一个ArrayList来存东西，我就默认ArrayList的存取都为恒定值
然后昨天被面试官质疑了
说我用ArrayList的insertion是O(n)的操作，所以实际的time complexity比我估计的
大很多
我想问一下这种情况多见么？
那我岂不是还要熟悉某个特定语言中数据结构的怎么实现的？ |
s**x
发帖数: 7506 | 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*******b
发帖数: 2586 | 3 不用担心，不懂的永远用不到。常用到的肯定都会。
写java了还关心什么数据结构，不差那点效率
【在 d**k 的大作中提到】
: 之前我计算时间复杂度都只是考虑到算法本需要的时间
: 比如说我在实现中用一个ArrayList来存东西，我就默认ArrayList的存取都为恒定值
: 然后昨天被面试官质疑了
: 说我用ArrayList的insertion是O(n)的操作，所以实际的time complexity比我估计的
: 大很多
: 我想问一下这种情况多见么？
: 那我岂不是还要熟悉某个特定语言中数据结构的怎么实现的？
|
d**k
发帖数: 797 | 4 问题是他考阿
我算法平时都不用的
【在 l*******b 的大作中提到】
: 不用担心，不懂的永远用不到。常用到的肯定都会。
: 写java了还关心什么数据结构，不差那点效率
|
d**k
发帖数: 797 | 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****e
发帖数: 54598 | 6 arraylist复杂度是o(n)那是最糟糕的情况
这个考官也是不懂
arraylist的insert明明是o(1) amortized
因为list本身有长度，如果超过了，需要扩充内存
但是平均起来是个常量
这个题目也不少太少见，见过几次 |
d**k
发帖数: 797 | 7 谢谢
不知道JAVA具体怎么实现的
【在 z****e 的大作中提到】
: arraylist复杂度是o(n)那是最糟糕的情况
: 这个考官也是不懂
: arraylist的insert明明是o(1) amortized
: 因为list本身有长度，如果超过了，需要扩充内存
: 但是平均起来是个常量
: 这个题目也不少太少见，见过几次
|
z****e
发帖数: 54598 | 8 你是不是用了很多arraylist.add(0,object)？
单纯的add(object)就是o(1) amortized |
d**k
发帖数: 797 | 9 我就是用了add 而已
他问我ArrayList的add是什么时间的
我张口就,常数阿
他表示很质疑
【在 z****e 的大作中提到】
: 你是不是用了很多arraylist.add(0,object)？
: 单纯的add(object)就是o(1) amortized
|
z****e
发帖数: 54598 | 10 那这个面官真够烂的，你说常数是对的
就是这个常数复杂度里面有点文章可以做就是了
http://stackoverflow.com/questions/5846183/arraylist-vs-linkedl
【在 d**k 的大作中提到】
: 我就是用了add 而已
: 他问我ArrayList的add是什么时间的
: 我张口就,常数阿
: 他表示很质疑
|
|
|
l*******b
发帖数: 2586 | 11 要理解面试官也是背了几页培训资料装门面，结果还背错了 :)
【在 z****e 的大作中提到】
: 那这个面官真够烂的，你说常数是对的
: 就是这个常数复杂度里面有点文章可以做就是了
: http://stackoverflow.com/questions/5846183/arraylist-vs-linkedl
|
l*****a
发帖数: 14598 | 12 你是说古路旁的面试观烂？
【在 z****e 的大作中提到】
: 那这个面官真够烂的，你说常数是对的
: 就是这个常数复杂度里面有点文章可以做就是了
: http://stackoverflow.com/questions/5846183/arraylist-vs-linkedl
|
z****e
发帖数: 54598 | 13 那你说，楼主妹子说arraylist的复杂度说错了吗？
【在 l*****a 的大作中提到】
: 你是说古路旁的面试观烂？
|
q*c
发帖数: 9453 | 14 虽然没错， 但是是胡乱蒙的， 所以别人一追问就露怯了。。。
【在 z****e 的大作中提到】
: 那你说，楼主妹子说arraylist的复杂度说错了吗？
|
z****e
发帖数: 54598 | 15 比起说成是o(n)的面官，我觉得这个蒙的直觉还更靠谱
arraylist被蒙成array基本上对
但是如果想成是linkedlist，那就是个错误了
【在 q*c 的大作中提到】
: 虽然没错， 但是是胡乱蒙的， 所以别人一追问就露怯了。。。
|
a********m
发帖数: 15480 | 16 ArrayList的存取是O(n)吧。俺怎么觉得面试官没说错。append可以勉强算o(1)，但是
lz明明说了是insert呀。 |
a********m
发帖数: 15480 | 17 复杂度效率和overhead效率是两码事。复杂度效率当然需要知道。
【在 l*******b 的大作中提到】
: 不用担心，不懂的永远用不到。常用到的肯定都会。
: 写java了还关心什么数据结构，不差那点效率
|
P******r
发帖数: 1342 | 18 ArrayList 的 Insert 是 O(n)吧。 add 才是O(1)。
不然还要什么hashlinkedlist干嘛 |
d**k
发帖数: 797 | 19 用的是add
【在 P******r 的大作中提到】
: ArrayList 的 Insert 是 O(n)吧。 add 才是O(1)。
: 不然还要什么hashlinkedlist干嘛
|
d**k
发帖数: 797 | 20 那我们一般分析时间效率要不要考虑overhead效率？
还是就算复杂度效率就可以了？
【在 a********m 的大作中提到】
: 复杂度效率和overhead效率是两码事。复杂度效率当然需要知道。
|
|
|
a********m
发帖数: 15480 | 21 overhead只是常数，慢点总是有限，区别是3秒还是4秒这种。算法复杂度是数量级问题
，区别是3秒还是3年的问题。big o里面常数都可以忽略。overhead一般在这部分。
【在 d**k 的大作中提到】
: 那我们一般分析时间效率要不要考虑overhead效率？
: 还是就算复杂度效率就可以了？
|
z****e
发帖数: 54598 | 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****e
发帖数: 54598 | 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****e
发帖数: 54598 | 24 ft
去哪里来的hashlinkedlist这个类
听说过linkedhashmap和linkedhashset
第一次听说hash跟list扯上关系的
你说的是linkedlist吧，这个不常用
【在 P******r 的大作中提到】
: ArrayList 的 Insert 是 O(n)吧。 add 才是O(1)。
: 不然还要什么hashlinkedlist干嘛
|
