大小为 n 的初始化列表的复杂性？

Question

我需要创建一个列表，其中 n 个项目都等于 0，我使用了这个方法：

list = [0] * n

时间复杂度是O(n)还是O(1)?

如果是 O(n)，是否可以用 O(1) 的复杂度来实现这个列表？

Answer 1

创建 n 个零的（密集）列表无法在 O(1) 中完成。您唯一的选择是查看一些稀疏或惰性数据结构。根据您要使用它的目的，一个选项可能是 itertools.repeat().

a = itertools.repeat(0, n)

将在 O(1) 中执行。当然，迭代它仍然是 O(n).

Answer 2

您也可以为生成器推出自己的方法：

def foo(num, times):
    for a in range(0, times):
        yield num

在我的机器上分析后：

import timeit

code = """
def foo(num, times):
    for a in range(0, times):
        yield num
"""
print timeit.timeit("foo(0,1)", setup=code)
print timeit.timeit("foo(0,2**8)", setup=code)

# 0.310677051544
# 0.32208776474

Answer 3

在 O(1) 时间内分配大对象的一种方法可以是（取决于您的底层操作系统）mmap.mmap，请参阅 https://docs.python.org/2/library/mmap.html。但是，它并不是具有所有灵活性的 list -- 它的行为更像是一个可变的字符数组。

有时这仍然会有帮助。在最近的Python3版本中，可以在mmap的结果上放一个memoryview，而e.b调用.cast('L')获取相同内存的视图作为整数序列（两个操作都是 O(1)）。仍然不是一个列表 -- 你没有得到 list 的丰富的灵活性和一整套的方法 -- 但是，更有可能是有帮助的...

补充：然而，这确实让我想起了许多年前，当时我正在努力将一个大型 CAD 应用程序移植到当时全新的 AIX 版本和基于 Power 的 IBM 工作站。 malloc 基本上是瞬时的——内核只是在 CPU.

中使用内存映射硬件在幕后做一些魔术

但是...实际上正在访问 一个远在 malloced 区域的项目（比如 N 字节构成它的开始) 第一次可能需要 O(N)，因为所有需要的页面实际上都已分配——如果系统实际上无法在您的进程地址 space 中找到或释放那么多页面，甚至可能导致崩溃（ IOW，malloc 首先是 "overcommitting" 内存！）。

正如您可以想象的那样，这对最初为更传统的 malloc 实现开发的应用程序造成了严重破坏：该应用程序检查了 malloc 的 return 值——如果为 0，则它采取适当的补救措施（最坏的情况，只是让用户知道由于内存不足而无法执行他们想要的操作）；否则，它假设它刚刚分配的内存实际上是......有时最终会在"random"点崩溃:-)。

解决方案只是中等难度——将 malloc 包装到一个函数中，后缀实际上触及 "nominally allocated" 页面的正确子集，以确保它们实际上都在那里（它 was 很难捕捉到这种时候可能出现的低级错误，但最终我设法找到了一种方法，我记得有一点汇编语言编码）。当然，这个 did 又把包裹的 malloc O(N) 搞了一遍……天下没有免费的午餐，谁会有想过吗？！-)

我不确定 mmap.mmap(-1, lotsofbytes) 从这个角度来看在您感兴趣的所有平台上实际上是如何表现的——我想这没什么，但实际上是在做实验！-）（如果它确实提供免费午餐，至少在流行的平台上是这样，现在值得庆祝:-)。

大小为 n 的初始化列表的复杂性？

Complexity of initialize list of size n?

python

time-complexity