स्क्वायर मैट्रिक्स गुणा की समय जटिलता क्यों ओ (एन^3) के रूप में परिभाषित की गई है?

Question

मैं इसे कई स्रोतों (ऑनलाइन और पुस्तकों) में मिला हूं - वर्ग मैट्रिक्स गुणा के चलने का समय आकार एनएक्सएन के मैट्रिस के लिए ओ (एन^3) है। (उदाहरण - matrix multiplication algorithm time complexity)

यह कथन इंगित करेगा कि इस गुणा प्रक्रिया के चलने वाले समय पर ऊपरी बाउंड सीएन^3 है जहां सी कुछ स्थिर और n> n0 है जहां n0 कुछ इनपुट है जिसके आगे यह ऊपरी सीमा सच है। (http://en.wikipedia.org/wiki/Big_O_notation और What is the difference between Θ(n) and O(n)?) समस्या यह है कि, मैं स्थिरांक सी और एन 0 के मान प्राप्त नहीं कर सकता।

मेरे सवालों -

1. कोई बयान के लिए एक गणितीय प्रमाण 'वर्ग मैट्रिक्स गुणन का बड़ा ओह है O (n^3)' दे सकते हैं?

2. सी और एन 0 के मूल्य क्या हैं?

Answer 1

1. वहाँ एक दूसरे को 0 से n-1 (या 1 एन करने के लिए) प्रत्येक (के रूप में in the link you provided देखा जा सकता है, भले ही यह पूरी तरह से सही नहीं है), इस में जो परिणाम के लिए जा रहा भीतर छोरों के लिए 3 हैं ओ (एन)। इसे उचित प्रमाण में औपचारिक बनाना पर्याप्त आसान होना चाहिए।

2. ए) औपचारिक प्रमाण के लिए, संचालन के कुछ सेट के संदर्भ में चलने का समय परिभाषित किया जाना चाहिए, आमतौर पर किसी भी अंकगणितीय ऑपरेशन के लिए लिया जाता है। छोरों के लिए 3 के अंदर 2 अंकगणितीय आपरेशनों (1 गुणा, 1 इसके अलावा), इस प्रकार हम 2.n3 मिलता है, इस प्रकार सी = 2.

   ख) N0 = 0 रहे हैं, क्योंकि इस एन = 1

से सच है

ध्यान दें कि, चूंकि बड़े-ओ सिर्फ ऊपरी बाउंड हैं, हम यह भी कह सकते हैं कि इस एल्गोरिदम की जटिलता ओ (एन ^के) किसी भी के> = 3 के लिए है (यदि हम बड़े- थेटा नोटेशन)। हम क्रमश: 2 और 0 से अधिक मूल्य के लिए सी और एन 0 भी ले सकते हैं (क्योंकि आवश्यकता को सबसे कम संभव मूल्यों को नहीं ढूंढना है)।