时间与空间矢量点积计算的复杂

Question

什么是一种算法，其与长度n计算两个矢量之间的点积的时间和空间复杂？

Answer 1

如果2个载体是a = [a1, a2, ... , an]和b = [b1, b2, ... , bn]，然后

点积是通过a.b = a1 * b1 + a2 * b2 + ... + an * bn

给出为了计算这一点，我们必须执行n乘法和加法(n-1)。 （我假设这是你所指的点积算法）。

假设乘法和加法是常数运算，因此时间复杂度为O(n) + O(n) = O(n)。

我们需要计算过程中唯一的辅助空间是拿“局部点积到目前为止”和计算的最后一个产品，即ai * bi。

假设我们可以在恒定空间中保存两个值，因此空间复杂度为O(1) + O(1) = O(1)。