帮帮我！ 这是一种算法，其计算之间与长度为n的矢量dotproduct的时间和空间复杂度。 ？

Help me! What is the time and space complexity of an algorithm, which calculates the dotproduct between to vectors with the length n. ?

推荐答案

如果2个向量 A = [A1，A2，...，一] 和 B = [B1，B2，......，BN] ，然后

该点产品是由给出AB = A1 * B1 + A2 * B2 + ... +一* BN

要计算这个，我们必须执行 N 乘法和（N-1）补充。 （我认为这是点积算法，你指的是）。

To compute this, we must perform n multiplications and (n-1) additions. (I assume that this is the dot-product algorithm you are referring to).

假定乘法和加法是恒定时操作， 因此，时间复杂度为 O（N）+ O（N）=为O（n）。

Assuming that multiplication and addition are constant-time operations, the time-complexity is therefore O(n) + O(n) = O(n).

我们需要的只是辅助空间的计算期间是拿部分点积至今'和计算的最后一个产品，即艾*双向。

The only auxiliary space we require during the computation is to hold the 'partial dot-product so far' and the last product computed, i.e. ai * bi.

假设我们可以在不断的空间容纳两个值， 因此，空间复杂度为 O（1）+ O（1）= 0（1）。

Assuming we can hold both values in constant-space, the space complexity is therefore O(1) + O(1) = O(1).