मैंने मैट्रिक्स गुणा पर एक सफलता के बारे में एक लेख पढ़ा है; एक एल्गोरिदम जो ओ (एन^2.373) है। लेकिन मुझे लगता है कि मैट्रिक्स गुणा कुछ ऐसा है जिसे समांतर किया जा सकता है। इसलिए, अगर हम कभी भी हज़ारवां कोर प्रोसेसर का उत्पादन शुरू करते हैं, तो क्या यह अप्रासंगिक हो जाएगा? चीजें कैसे बदलेगी?समांतरता से प्रभावित बड़े-ओ नोटेशन पर रेट किए गए एल्गोरिदम हैं?
यदि क्वांटम कंप्यूटिंग कुछ दिन व्यावहारिक कुछ आता है, तो हाँ, एल्गोरिदम की जटिलता बदलेगी।
इस बीच, एक निश्चित संख्या में प्रोसेसर के साथ एक एल्गोरिदम समानांतर, बस अपने रनटाइम आनुपातिक (और सबसे अच्छा मामले में, प्रत्येक प्रोसेसर में किए गए कार्यों के बीच कोई निर्भरता नहीं है) को विभाजित करता है। इसका मतलब है, रनटाइम को निरंतर विभाजित करना, और इसलिए जटिलता वही रहती है।
समांतर निष्पादन किसी विशेष एल्गोरिदम के लिए जटिलता की मूल बातें नहीं बदलता है - सबसे अच्छा, आप बस कुछ दिए गए आकार के लिए समय ले रहे हैं, और कोर की संख्या से विभाजित कर रहे हैं। यह निरंतर कारक द्वारा दिए गए आकार के लिए समय कम कर सकता है, लेकिन एल्गोरिदम की जटिलता पर इसका कोई प्रभाव नहीं पड़ता है।
उसी समय, समानांतर निष्पादन कभी-कभी बदलता है जो एल्गोरिदम आप विशेष कार्यों के लिए उपयोग करना चाहते हैं। सीरियल कोड में अच्छी तरह से काम करने वाले कुछ एल्गोरिदम बस समानांतर कार्यों में विभाजित नहीं होते हैं। अन्य जिनके पास जटिलता व्यावहारिक आकार की समस्याओं के लिए तेज़ी से हो सकती है क्योंकि वे समानांतर में बेहतर चलती हैं।
कोर की एक बड़ी संख्या के लिए, गणना की जटिलता सभी कोरों को गणना करने के लिए आवश्यक डेटा प्राप्त करने के लिए माध्यमिक हो सकती है। बड़े-ओ के अधिकांश कंप्यूटेशंस इन प्रभावों को एक धारावाहिक गणना के लिए खाते में नहीं लेते हैं, लेकिन यह समांतर गणनाओं के लिए काफी महत्वपूर्ण हो सकता है, खासतौर पर समांतर मशीनों के कुछ मॉडलों के लिए जो सभी नोड्स में समान पहुंच नहीं देते हैं।
Amdahl's law, समस्या की एक ही आकार के लिए रखकर चलाना कोर (सैद्धांतिक) की संख्या में वृद्धि के साथ वापसी ह्रासमान के एक बिंदु पर आ जाएगा। हकीकत में, समांतरता की एक निश्चित डिग्री से, समांतरता के उपरांत वास्तव में कार्यक्रम के प्रदर्शन को कम कर देगा।
हालांकि, Gustafson's law द्वारा, कोर की संख्या में वृद्धि वास्तव में समस्या के आकार के रूप में मदद करता है। क्लस्टर कंप्यूटिंग के पीछे यह प्रेरणा है। चूंकि हमारे पास अधिक कंप्यूटिंग शक्ति है, हम समानांतरता की सहायता से बड़े पैमाने पर या बेहतर परिशुद्धता से समस्या का सामना कर सकते हैं।
एल्गोरिदम जो हम सीखते हैं वह पैरालाइज़ेबल हो सकता है या नहीं। कभी-कभी, समान कार्य में कुशलतापूर्वक निष्पादित करने के लिए एक अलग एल्गोरिदम का उपयोग किया जाना चाहिए। किसी भी तरह से, बिग-ओ नोटेशन को समांतर मामले के लिए फिर से विश्लेषण करना चाहिए ताकि एल्गोरिदम की समय जटिलता पर समांतरता के प्रभाव को ध्यान में रखा जा सके।
वह एल्गोरिदम केवल सैद्धांतिक सफलता है; जहां तक मुझे पता है कि यहां तक कि कॉपरस्मिथ-विनोग्राड एल्गोरिदम का प्रयोग अभ्यास में नहीं किया जाता है। – sdcvvc
जाल आधारित आर्किटेक्चर के लिए एन लॉग^2 (एन) एल्गोरिदम है, मैट्रिक्स गुणा (सैद्धांतिक रूप से) के लिए एन प्रोसेसर के साथ, बहुत सारे एल्गोरिदम भी हैं जो उनके सामान्य 'ओ' से स्वतंत्र होते हैं, जब आप समानांतर के बारे में सोचना चाहते हैं एल्गोरिदम, आपको अन्य तरीकों के बारे में सोचना चाहिए, सामान्य तरीके सामान्य रूप से बेकार हैं। –