algorithm - 矢量点积计算的时间和空间复杂度

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)。