什麼是一種算法,其與長度n計算兩個矢量之間的點積的時間和空間複雜?時間與空間矢量點積計算的複雜
回答
如果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)
。
謝謝。但我需要用n表示。所以時間複雜度將是n +(n-1)和空間2n? – 2010-09-19 01:15:24
big-theta也隱藏常量(在這種情況下,O = big-Theta)。你的意思可能是*等值*。 – 2010-09-19 01:53:13
@Alexandre C:我同意 - 在這種情況下,我提供了Big Theta。是不是暗示(雖然閱讀我的評論,這聽起來像),只是OP是否意識到這實際上是一個緊張的限制。 – Ani 2010-09-19 02:32:59
- 1. 時間複雜度和空間複雜度,如何計算空間複雜度
- 2. 計算函數的空間複雜度和時間複雜度
- 3. 計算時間複雜度
- 4. 時間計算複雜度?
- 5. 計算時間複雜度
- 6. 計算時間複雜度
- 7. 計算時間和空間複雜度來刪除重複項
- 8. 如何計算算法時間複雜
- 9. 時間和空間複雜
- 10. 簡單的時間複雜度計算
- 11. 計算時間代碼的複雜性
- 12. 計算中間矢量角
- 13. 用大O計算時間複雜度
- 14. 計算時間複雜度示例
- 15. 計算不規則空間的面積
- 16. 計算BST節點移除的時間複雜度
- 17. 算法複雜度時間
- 18. 迴文算法的時間和空間複雜
- 19. 計算懶惰評估語言中的時間空間複雜度
- 20. 時間和空間複雜的語言複雜性
- 21. 遞歸算法的空間複雜度
- 22. 算法的複雜性能和空間
- 23. 算法算法的時間複雜度
- 24. 計算二維矢量的交叉積
- 25. 卷積的計算複雜度
- 26. 以大O爲反向矢量的時間複雜度
- 27. 如何減少轉換矢量到墊的時間複雜度
- 28. C++ - 改進複雜數學運算的計算時間
- 29. 計算遞歸算法的時間複雜度。
- 30. 算法的運行時間計算/複雜度
你的老師探查是一個點積是一個線性時間'O(N)'操作,其中n是兩個向量的長度。這假設你考慮乘法和加法作爲恆定時間操作。技術上'*'和'+'不是固定時間。如果要吹毛求疵,並與圖靈機的時間複雜度超精密,然後隨着數字的平均長度乘以和'了'隨着數字的平均長度被添加定義'M'。複雜度變爲:'爲O(n *(平方公尺1.465)+((N-1)*日誌的(a)))',其摺疊到:'O(N * M + N *日誌的(a))'。 – 2017-03-25 03:03:18