numpy库中是否有大O复杂性列表？

Question

我正在对算法进行时间复杂度分析,需要知道某些numpy操作有哪些复杂性.

对于一些人,我认为它们与基础数学运算相匹配.就像np.dot(array1, array2)是O(n).对于其他人,我不太确定.例如,是np.array(my_array)O(1)？还是O(n)？它只是重新分配一个指针,还是在列表上迭代并复制出每个值？

我想确定每个操作的复杂性.有什么地方我可以找到这些信息吗？或者我应该假设它们与数学运算相匹配？

Answer 1

BigO 复杂性不常用于 Python 和 numpy。它是衡量代码如何随问题规模变化的指标。这在像 C 这样的编译语言中很有用。但这里的代码是解释型 Python 和编译型代码的混合。两者都可以有相同的 bigO，但解释版本会慢几个数量级。这就是为什么大多数关于提高 numpy 速度的 SO 问题，谈论“删除循环”和“矢量化”。

也很少有操作是纯 O(n)；大多数是混合的。有一个设置成本，加上每个元素的成本。如果每个元素的成本很小，则设置成本占主导地位。

如果从列表开始，对列表进行迭代通常会更快，因为将列表转换为数组会产生大量开销 (O(n))。

如果您已经有数组，则尽可能避免（python 级别）迭代。迭代是大多数计算的一部分，但是 numpy 可以让您在更快的编译代码（更快的 O(n)）中完成很多工作。

在某些时候，您必须了解 numpy 如何存储其数组。view和之间的区别copy很重要。一个视图实际上是 O(1)，一个副本 O(n)。

通常，您会看到 SO 答案进行timeit速度比较。我经常添加一个警告，即结果可能会随着问题的大小而变化。更好的答案将计时各种大小的问题，并在一个漂亮的图上显示结果。结果通常是直线 (O(n)) 和曲线（O(1) 和 O(n) 分量的不同混合）的混合。

您专门询问了np.array. 以下是一些示例时间：

In [134]: %%timeit alist = list(range(1000))
     ...: np.array(alist)
67.9 µs ± 839 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [135]: %%timeit alist = list(range(10))
     ...: np.array(alist)

2.19 µs ± 9.88 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [136]: %%timeit alist = list(range(2000))
     ...: np.array(alist)
134 µs ± 1.98 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

复制一个数组：

In [137]: %%timeit alist = list(range(2000)); arr=np.array(alist)
     ...: np.array(arr)
1.77 µs ± 24.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

没有副本：

In [138]: %%timeit alist = list(range(2000)); arr=np.array(alist)
     ...: np.array(arr, copy=False) 
237 ns ± 1.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

从字符串列表中：

In [139]: %%timeit alist = [str(i) for i in range(2000)]
     ...: np.array(alist, dtype=int)
286 µs ± 4.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

几乎所有的计算numpy都是 O(n)。如果涉及到数组的每个元素呢，速度将取决于数组的大小。一些数组操作是 O(1)，例如整形，因为它们实际上不对数据做任何事情；它们会改变形状和步幅等属性。

搜索问题通常比 O(n) 增长得更快；通常numpy不是解决这类问题的最佳选择。聪明的使用 Python 列表和字典可以更快。

Answer 2

对于特定示例，np.array(my_array)因为它需要遍历my_array的所有元素、分配内存并初始化值，所以它发生在线性时间内。

python中有一个模块big_O，可以用来从函数的执行时间来分析函数的复杂度。

请参阅此链接了解更多信息