Gæs*_*æst 6 algorithm complexity-theory vector
What is the time and space complexity of an algorithm, which calculates the dot product between two vectors with the length n?
Ani*_*Ani 11
如果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).