मैट्रिक्स अतिरिक्तता की जटिलता क्या है?

Question

मुझे some mentions in another question of matrix addition being a quadratic operation मिला है। लेकिन मुझे लगता है कि यह रैखिक है।

यदि मैं मैट्रिक्स के आकार को दोगुना करता हूं, तो मुझे जोड़ों को दोगुना करने की आवश्यकता होती है, चौगुनी नहीं।

मुख्य विचलन बिंदु समस्या का आकार क्या प्रतीत होता है। मेरे लिए, यह मैट्रिक्स में तत्वों की संख्या है। अन्य सोचते हैं कि यह कॉलम या लाइनों की संख्या है, इसलिए O(n^2) जटिलता।

एक चौथाई ऑपरेशन के रूप में इसे देखने के साथ मुझे एक और समस्या यह है कि इसका मतलब है कि 3-आयामी मैट्रिस जोड़ना क्यूबिक है, और 4-आयामी मैट्रिस जोड़ना O(n^4), आदि है, भले ही इन सभी समस्याओं को समस्या में कम किया जा सके दो वैक्टर जोड़ने का, जिसमें स्पष्ट रूप से रैखिक समाधान है।

क्या मैं सही या गलत हूँ? यदि गलत है, क्यों?

Answer 1

जैसा कि आपने पहले ही उल्लेख किया है, यह समस्या आकार की आपकी परिभाषा पर निर्भर करता है: क्या यह तत्वों की कुल संख्या या मैट्रिक्स की चौड़ाई/ऊंचाई है। जो भी सही है वह वास्तव में बड़ी समस्या पर निर्भर करता है जिसमें मैट्रिक्स अतिरिक्त हिस्सा है।

एनबी: कुछ हार्डवेयर (जीपीयू, वेक्टर मशीन, आदि) पर अतिरिक्त वृद्धि अपेक्षा से तेज़ी से चल सकती है (भले ही जटिलता अभी भी वही है, नीचे चर्चा देखें), क्योंकि हार्डवेयर एक चरण में कई अतिरिक्त प्रदर्शन कर सकता है। बाध्य समस्या के आकार के लिए (जैसे3) यह एक कदम भी हो सकता है।

Answer 2

यह एम (एम * एन) एम पंक्तियों और एन कॉलम के साथ 2-आयामी मैट्रिक्स के लिए है।

या आप कह सकते हैं कि यह ओ (एल) है जहां एल तत्वों की कुल संख्या है। सामान्य मामले कार्यान्वयन के

Answer 3

थिंक:

for 1 : n 
for 1 : m 
    c[i][j] = a[i][j] + b[i][j] 

अगर हम साधारण वर्ग मैट्रिक्स ले, कि nxn अतिरिक्त

Answer 4

आमतौर पर समस्या "आकार एन की" वर्ग मैट्रिक्स का उपयोग कर परिभाषित किया गया है, जिसका अर्थ है NxN है । उस परिभाषा के अनुसार, मैट्रिक्स अतिरिक्त एक ओ (एन^2) है क्योंकि आपको प्रत्येक बार एनएक्सएन तत्वों में से प्रत्येक बार जाना चाहिए।

उसी परिभाषा के अनुसार, मैट्रिक्स गुणा (वर्ग एनएक्सएन मैट्रिस का उपयोग करके) ओ (एन^3) है क्योंकि आपको उत्पाद मैट्रिक्स में प्रत्येक एनएक्सएन तत्वों की गणना करने के लिए प्रत्येक स्रोत मैट्रिक्स में एन तत्वों को देखने की आवश्यकता है।

आम तौर पर, सभी मैट्रिक्स परिचालनों में ओ (एन^2) की निचली सीमा होती है क्योंकि आपको पूरे मैट्रिक्स से जुड़े किसी भी चीज़ की गणना करने के लिए कम से कम एक बार प्रत्येक तत्व पर जाना चाहिए।