`numpy.argmax()` 的理论平均案例运行时复杂度

Question

我在看

numpy.argmax

函数的代码。我很困惑

numpy

为

argmax

函数维护哪个数据结构。

https://numpy.org/doc/stable/reference/generated/numpy.argmax.html

最后，我想知道原始数据类型的numpy argmax函数的

理论平均运行时间

复杂度是多少。一般情况下是

O(logN)

还是

O(N)

？

这也可能是一个相关的问题：较慢的 numpy.argmax/argmin 的更快替代方案

提前致谢。

Answer 1

这里是使用

benchit

的性能分析：

def m(x):
  return np.argmax(x)

in_ = [np.random.rand(n) for n in [10,100,1000,10000]]

如您所见，它应该是

O(N)

。您遍历数组一次以找到最大值。

Answer 2

要在这里添加回复，因为数字自然取决于您的硬件，这应该为其他人提供一些见解。这是一个 benchit 结果，显示了内存结构如何影响结果，但是线性部分开始于大小为 10,000 左右的向量，比例为 1:1，对于大于 10,000 个样本的向量，一个很好的近似值是向量中每个值 5e-10 .