将列表拆分成多个列表以获得加速？

Question

假设我的列表是关于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倍!我认为难以置信,所以我的问题:

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

Answer 1

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