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

wn9m85ua 于 2023-04-06 发布在其他

关注(0)|答案(2)|浏览(153)

我正在看numpy.argmax函数的代码。我很困惑numpy为argmax函数维护的是哪种数据结构。
https://numpy.org/doc/stable/reference/generated/numpy.argmax.html
最后，我想知道numpy argmax函数对于原始数据类型的理论平均情况运行时间复杂度是多少，平均情况下是O(logN)还是O(N)？
这也可能是一个相关的问题：Faster alternatives to numpy.argmax/argmin which is slow
先谢谢你了。

2条答案

下面是使用benchit的性能分析：

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

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

正如你所看到的，它是O(N)，因为它应该是。你迭代数组一次，以找到最大值。

这里要添加一个响应，因为数字自然会取决于您的硬件，这应该为其他人提供一些见解。这里是一个基准测试结果，显示内存结构也会影响结果，但线性部分在大小约为10，000的向量中起作用，具有1：1的缩放比例，并且向量〉10，000个样本的良好近似值是向量中每个值的5e-10。