python list 随机访问的复杂度？

retuor

UID: 924
帖子: 135
积分: 310
在线时间: 1 天 1 小时

1^# retuor 发表于 2008-01-15 10:58

python list 随机访问的复杂度？

python list 可以象数组那样随机访问。但访问一个数组元素的消耗是 O(1) 的，访问 python list 的一个元素也是 O(1) 的吗？

thinkc

UID: 31061
帖子: 91
积分: 209
在线时间: 11 小时

2^# thinkc 发表于 2008-01-15 11:37

O(1) 是什么意思?

retuor

UID: 924
帖子: 135
积分: 310
在线时间: 1 天 1 小时

3^# retuor 发表于 2008-01-15 11:54

O(1) 是指访问时间是个常数，跟访问的是第几个元素没有关系。

比如，c 语言的数组 a[100]，访问 a[0] 的时间与访问 a[99] 的时间是一样的。

在 python 中，一个长度为 100 的列表，访问第 1 个元素的时间跟访问第 100 个元素花费的时间是大致一样的吗？

如果是单链表，则定位第 n 个节点的时间是定位第一个节点的 n 倍。

不知道 python 的 list 是怎么实现的？

thinkc

UID: 31061
帖子: 91
积分: 209
在线时间: 11 小时

4^# thinkc 发表于 2008-01-15 12:30

写程序验证一下吧,相同的一个包含100个item的list,起两个线程,一个读[0],另一个读[100],反复读1000次,比较两个线程使用的总时间是否相同,比较笨的验证办法

fuqiang_huang

UID: 2252
帖子: 68
积分: 156
在线时间: 6 小时

5^# fuqiang_huang 发表于 2008-01-16 10:17

Python-2.5.1/Objects/listobject.c 查一下源文件就明白了.