我需要创建一个包含 n 个项目的列表，所有项目都等于 0，我使用了这个方法:
list = [0] * n
时间复杂度是O(n)还是O(1)？
如果是 O(n)，是否可以通过 O(1) 复杂度实现此列表？
最佳答案
在 O(1) 时间内分配大对象的一种方法可以是(取决于您的底层操作系统)mmap.mmap，请参阅 https://docs.python.org/2/library/mmap.html .然而，它不是一个具有所有灵 active 的列表——它的行为更像是一个可变的字符数组。
有时这仍然会有帮助。在最近的 Python 3 版本中，你可以在 mmap 的结果上放置一个 memoryview，然后 e.b 调用 .cast('L') 来获得与整数序列相同的内存 View (两种操作都是 O(1))。 仍然不是一个列表——你没有得到一个列表的丰富的灵 active 和一整套的方法——但是，更有可能是有用的...
补充:然而，这确实让我想起了许多年前，当时我正在努力将一个大型 CAD 应用程序移植到当时全新的 AIX 版本和基于 Power 的 IBM 工作站。 malloc 本质上是即时的——内核只是在幕后使用 CPU 中的内存映射硬件执行一些操作。
但是...实际上是第一次访问远在malloced 区域中的项目(比如 N 字节构成它的开始)可能需要 O(N) 因为所有需要的页面实际上都已分配 - 如果系统实际上无法在您的进程地址空间中找到或释放那么多页面，甚至可能导致崩溃(IOW，那malloc 首先是“过度使用”内存!)。
正如您可以想象的那样，这对最初为更传统的 malloc 实现开发的应用程序造成了严重破坏:该应用程序检查了 malloc 的返回值——如果为 0，则它采取适当的补救措施(最坏的情况，只是让用户知道由于内存不足而无法执行他们想要的操作)；否则，它会假定它刚刚分配的内存是实际存在的......有时最终会在路上的“随机”点崩溃:-)。
解决方案只是中等难度——将 malloc 包装到一个函数中，后缀实际上触及“名义上分配”页面的正确子集，以确保它们实际上都在那里(它 很难捕捉到这种时候可能出现的低级错误，但最终我设法找到了一种方法，我记得使用一点汇编语言编码)。当然，这 确实 使包装的 malloc O(N) 再次出现......似乎没有这样的东西免费午餐，谁会想到？!-)
我不确定从这个角度来看，mmap.mmap(-1, lotsofbytes) 在您感兴趣的所有平台上的实际行为如何——我猜除了实际实验之外别无他法! -)(如果它确实提供免费午餐，至少在流行的平台上，现在那将值得庆祝:-)。
关于python - 大小为 n 的初始化列表的复杂性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27966221/