时间戳

首页 > 解决方案 > 在python中将列表分成两部分的时间复杂度

python - 在python中将列表分成两部分的时间复杂度

问题描述

像这样的切片操作some_list[i:i+k] 需要 O(k) 时间，因为它必须在根据this创建新列表时从 i 迭代到 i+k 。

我对列表切片操作的时间复杂度感到困惑，例如chunk_1, chunk_2 = some_list[:chunk_size], some_list[chunk_size:].

相应地，这种操作的总体时间复杂度应该是多少：

while some_list:
    chunk, some_list = some_list[:chunk_size], some_list[chunk_size:]

我想，在这个操作中，将元素复制到新块中的成本也会增加总成本。

有没有更好的方法可以将大列表分成大小均匀的块？

更新：

做了一些分析来检查 while 循环是否是 O(n^2) 操作。添加结果：

In [1]: def chunk(l, c):
   ...:     while l:
   ...:         l_c, l = l[:c], l[c:]
   ...:

In [2]: l = list(range(1000))

In [3]: %timeit chunk(l, 10)
134 µs ± 702 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [4]: l = list(range(10000))

In [5]: %timeit chunk(l, 10)
16.1 ms ± 99.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [6]: l = list(range(100000))

In [7]: %timeit chunk(l, 10)
1.91 s ± 14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

就时间复杂度而言，有人可以提出更好的方法吗？列表中的数据不是数字的，所以不能使用 Numpy。

标签： pythonlisttime-complexitybig-o

解决方案

您可以使用generator. generator将更有效率，因为它将yield块：

def chunks(lst, n):
    """Yield successive n-sized chunks from lst."""
    for i in range(0, len(lst), n):
        yield lst[i:i + n]

在此处查看原始答案如何将列表拆分为大小均匀的块？

推荐阅读