[已解决]python是动态顺序表，可是感觉python的list的插入和删除操作的时间复杂度是O(1)呢？

Kara12

python是动态顺序表，可是感觉python的list的插入和删除操作的时间复杂度是O(1)呢？
但顺序表的插入和删除操作的时间复杂度不是O(n)吗？
求解惑！

最佳答案

月排行榜 / 总排行榜

sky

2018-1-24 17:29:50

Kara12 发表于 2018-1-24 17:28
1, 嗯，文档里的确写的append是O(1), insert是O(n)
2, 你这是用什么记得时间？

time.time() 插入前和插入后相减 前面都是0.0 你可以试试

跳转到最佳答案楼层

sky

https://wiki.python.org/moin/TimeComplexity

说明 感觉不准确
可以试着删了插 插了删几千万元素的列表
几千万次 试试 就不快了
------
这样 列表长度10 100 1000 10000这样长度插入一次的时间
明显列表越长时间也越长就感觉不对吧
我试了下 列表太长就卡死了

1. 1000000 0.0010027885437011719
   
2. 10000000 0.011012077331542969
   
3. 100000000 0.1261143684387207
   
4. ...
   

复制代码

后面就卡死了 怕死机果断断开了
列表短的时候确实很快

BngThea

不知道底层的算法怎么弄的
而且你怎么感觉出来的，时间复杂度为1

冰封雪舞

啥叫时间复杂度？

Kara12

sky 发表于 2018-1-24 15:48
https://wiki.python.org/moin/TimeComplexity

说明 感觉不准确

1, 嗯，文档里的确写的append是O(1), insert是O(n)
2, 你这是用什么记得时间？

sky

Kara12 发表于 2018-1-24 17:28
1, 嗯，文档里的确写的append是O(1), insert是O(n)
2, 你这是用什么记得时间？

time.time() 插入前和插入后相减 前面都是0.0 你可以试试

Kara12

sky 发表于 2018-1-24 17:29
time.time() 插入前和插入后相减 前面都是0.0 你可以试试

谢谢