दो निचले त्रिकोणीय matrices के गुणा की जटिलता

Question

मुझे पता है कि दो पूर्ण matrices के गुणा की निचली सीमा Ω (एन^2) है। Matrix multiplication

मैं यह साबित करने की कोशिश कर रहा हूं कि समस्या परिवर्तन विधि का उपयोग कर दो निचले त्रिकोणीय मैट्रिक्स के गुणा की निचली सीमा।

मेरी प्रारंभिक सोच यह है कि (1) निचले त्रिकोणीय मैट्रिक्स को बदलने के लिए, (2) इस तरह के परिवर्तन की समय जटिलता का अनुमान लगाएं।

T(lower_triangular_matrix_multiplication(n))+O(lower_triangular_matrix_transformation(n))>Ω(full_matrix_multiplication(n)) = Ω(n^2) 

अब, मैं केवल O(lower_triangular_matrix_transformation(n)) साबित करने के लिए है और मैं त्रिकोणीय मैट्रिक्स तो मैं बस इस त्रिकोणीय मैट्रिक्स खुद की भिन्नता से गुणा किया जाने एक पूर्ण मैट्रिक्स होने के लिए बनाने की जरूरत है, स्थानांतरित, सादगी के लिए कहते हैं।

कारण यह है कि निचले त्रिकोणीय मैट्रिक्स का वर्ग अभी भी एक निम्न त्रिकोणीय मैट्रिक्स है और इसके त्रिकोणीय विविधता से गुणा कम त्रिकोणीय मैट्रिक्स एक "पूर्ण मैट्रिक्स" है।

इसलिए मुझे केवल एक त्रिकोणीय मैट्रिक्स की जटिलता का विश्लेषण करने की आवश्यकता है जो इसके ट्रांसपोज़ड विविधता से गुणा हो।

कोई भी संकेत दे सकता है कि मेरी सोच "उचित" है या नहीं?

Answer 1

मैं सोच रहा था कि समाधान ए को ए + ए में बदलने के लिए हो सकता है। ट्रांसपोज़र और प्लस के संचालन की जटिलता दोनों ओ (एन^2) है। तो, ओ (low_triangular_matrix_transformation (n)) = n^2। ए ए और निम्न में से एक (ए + ए ') (ए + ए') भी Ω (एन^2), टी (low_triangular_matrix_multiplication (n))> Ω (full_matrix_multiplication (n)) -ओ (low_triangular_matrix_transformation (n)), जिसका अर्थ है कि त्रिभुज मैट्रिक्स की निचली सीमा और पूर्ण मैट्रिक्स में से एक समान है।

Q.E.D.

Answer 2

मुझे विश्वास नहीं है कि एल्गोरिदम का निर्माण करके कम सीमा के लिए पर्याप्त सबूत है, क्योंकि इसे अभी भी बाहर नहीं रखा जा सकता है कि कम जटिलता वाले एक अलग एल्गोरिदम मौजूद होगा।

यह स्पष्ट है कि निचली बाउंड ओ (एन^2) से अधिक नहीं होगी क्योंकि सामान्य गुणा हमेशा low_triangle_matrices (ltm) पर लागू होगी।

अब, एक अयस्क अधिक लेटम के लिए मनमानी मैट्रिक्स के किसी भी परिवर्तन के रूप में स्वयं ओ (एन^2) जटिलता का संचालन है, हम यह नहीं समझ सकते कि ऐसा कोई भी एल्गोरिदम मौजूद नहीं है।

तर्क की आपकी रूपरेखा यह सुझाव देती है कि जटिलताओं को जोड़ना "सामान्य" अंकगणितीय नियमों का पालन कर रहा है। यह मामला नहीं है!
परिणामस्वरूप जटिलता हमेशा कम से कम (एल्गोरिदम भागों की अधिकतम जटिलताओं) होती है।

तो आपकी तर्क ध्वनि नहीं लगती है।

आप निम्न में से एक कोशिश कर सकते:

1. कम जटिलता के साथ एक एल्गोरिथ्म का निर्माण (सबूत अस्तित्व होना)
   जब लक्ष्य है ओ (ltm) < O (n^2)
2. लगता है एक परिवर्तन जिसमें जटिलता < ओ (एन^2) है और यह एलटीएम उत्पन्न करता है। फिर एलटीएम गुणा के लिए कोई एल्गोरिदम जिसमें कम जटिलता जटिलता के साथ मनमानी मैट्रिक्स के लिए एक एल्गोरिदम प्रदान करेगी, यह आपके प्रारंभिक प्रस्ताव के विपरीत होगा।
   हालांकि, पर्याप्त कम जटिलता के परिवर्तन की आवश्यकता है। यदि यह ज्ञात नहीं है। तर्क प्रयोग योग्य नहीं है।

मेरे लिए ऐसा लगता है कि टी() + ओ()> ओ (एन^2) से कदम अच्छी तरह से ग्राउंड नहीं है। और इस निष्कर्ष को सिर्फ प्रमाण (ओ (एलटीएम)) को तोड़ना है।