3

假设我的列表是关于1,000,000条目的。要访问一个项目，时间将是O(500,000)，这对我来说似乎很长。

当我将列表拆分为多个列表时会发生什么？让我们看一个例子：
将列表分成 10 个部分，我将有一个列表如下：

splitted_list = [
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries]
]

访问一个项目的时间将是O(5) + O(50,000) = O(50,005)大约 1000% 的加速！

当拆分关于它的根的原始列表时，1000在这种情况下，这将给我们一个包含 1000 个列表的列表，其中包含另外 1000 个条目。

splitted_list = [
    [list with 1000 entries],
    [list with 1000 entries],
    [list with 1000 entries],
    [list with 1000 entries],
    ...
]

现在看一下访问项目的时间：

O(500) + O(500) = O(1000)
O(1000) < O(50,005) < O(500,000)

这是1000倍左右的最佳加速！难以置信，我想，所以我的问题是：

这是否也适用于实践，或者这只是理论？

4

3 回答 3

5

无论列表大小如何，从列表中按索引获取项目都是 O(1) 。

于 2011-08-11T11:19:55.227 回答
4

您的问题的答案是您正在考虑链表，其中每个元素都包含一个指向下一个元素的指针。它们具有 O(n) 索引，因为获取第 n 个元素的唯一方法是从头开始遍历列表。

您的想法与各种数据结构有关，其中最接近的可能是跳过列表。这是一种基于链表的数据结构，但具有节点的“高速公路”，这些节点向前跳过了列表的多个元素。优点是您可以沿着高速公路跑到列表的中间，然后在需要单个元素精度时下降到“较慢的车道”，从而提供 O(log n) 索引效率 - 与二叉树。_ 当然，缺点是执行其他链表操作（例如随机插入）更复杂（也更慢）。

然而，Python 列表在底层实现为动态增长的数组。它们具有 O(1) 索引，因为要获得第三个元素，您只需将三个（单位）添加到第一个元素的内存地址，而无需遍历其间的所有元素。

您可能对有关数据结构的 Wikipedia 文章感兴趣。

于 2011-08-11T11:52:56.500 回答
3

我假设您正在谈论在列表中查找元素。

如果您正在谈论将排序列表拆分为多个排序列表并带有指向它们的头部的指针，那么恭喜您，您几乎发现了 B 树。

如果这些列表确实是数组（即您有恒定时间随机访问），您也可以进行二分搜索。

于 2011-08-11T11:21:38.940 回答