時間與空間矢量點積計算的複雜

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