गुणात्मक, वर्ग रूट, लॉगरिदम, स्केलर और मैट्रिक्स उत्पाद जैसे मूल अंकगणितीय परिचालनों के व्यापक एल्गोरिदम के लिए बिग-ओ जटिलता क्या है?मूल अंकगणितीय परिचालनों की बिग ओ जटिलता
क्या बिग-ओ जटिलता के मामले में विदेशी एल्गोरिदम अधिक कुशल हैं, लेकिन व्यावहारिक समाधानों में बहुत व्यापक नहीं हैं (उदाहरण के लिए लोकप्रिय सॉफ्टवेयर पुस्तकालयों में लागू नहीं)?
देखें वर्ग मैट्रिक्स के http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
मैट्रिक्स उत्पाद:
वहाँ भी एक हे (एन 2.38) Coppersmith–Winograd algorithm है, लेकिन मैं यह बहुत बड़ा छिपा निरंतर की वजह से व्यापक फैल है नहीं लगता।
बिग पूर्णांक गुणन:
एक एन लॉग एन & मिडॉट भी हैं; 2 ओ (लॉग * एन) 2008 में प्रकाशित एल्गोरिदम लेकिन यह व्यापक होने के लिए बहुत नया था।
आम तौर पर भद्दा विधि सामान्य आकार के इनपुट के लिए पर्याप्त है।
यह दिलचस्प है, ओ (एन 2.38) ओ (एन³) से कितना तेज़ है। – psihodelia
दुर्भाग्य से, इसका उत्तर "यह निर्भर करता है"। जैसा कि विकिपीडिया आलेख का उल्लेख है, एल्गोरिदम का व्यापक रूप से उपयोग नहीं किया जाता है क्योंकि यह वास्तव में अव्यवहारिक रूप से भारी इनपुट के लिए रनटाइम में कमी का परिणाम देता है। –
प्रैक्टिस में, ओ (एन^2.38) एल्गोरिदम बिल्कुल तेज नहीं है, क्योंकि एल्गोरिदमिक जटिलता की तुलना में गति के लिए और भी कुछ है। – Pillsy
संचालन में जटिलता नहीं है, एल्गोरिदम करते हैं। उदाहरण के लिए, विभिन्न वर्ग रूट एल्गोरिदम हैं, और उनके पास अलग-अलग जटिलता होगी।
गुणा बिट्स के दो सरणी के बीच एक एल्गोरिदम है। जटिलता ओ (एन²) के साथ, अगर मुझे गलत नहीं लगता है। – Tronic
@ स्किलड्रिक: ओपी सबसे अधिक इस्तेमाल किए जाने वाले एल्गोरिदम के बारे में बात कर रहा है, इसलिए एक अर्थ में यह उत्तर अप्रासंगिक है। –
@ मॉरन: मुझे लगता है कि मैंने जवाब देने के बाद से सवाल थोड़ा संपादित किया है। – Skilldrick
आप ओ (1) के रूप में सबसे सरल संचालन पर विचार करेंगे क्योंकि आपका इनपुट आकार आमतौर पर तय किया जाता है (यानी 32- या 64-बिट्स)।
सामान्य परिस्थितियों में, आपका प्लेटफ़ॉर्म आपके इनपुट के "आकार" (यानी int = 0; और int b = Int32.MaxValue के बावजूद गुणा, वर्ग रूट, लॉगरिदम इत्यादि के लिए बिल्कुल वही ऑपरेशन करेगा। दोनों 32-बिट पूर्णांक)।
मैट्रिस को देखने या मनमाने ढंग से सटीक संख्याओं का प्रतिनिधित्व करने के बाद यह दिलचस्प हो जाता है, लेकिन किसी ने पहले ही विकिपीडिया सारांश को जोड़ा है, इसलिए मैं उसमें नहीं जाऊंगा।
बस "सामान्य" छोटी संख्याओं को गुणा करने के लिए Schönhage–Strassen का उपयोग न करें। यह मुझे रोएगा। सिर्फ इसलिए कि एक एल्गोरिथ्म हे है (n) यह बुरा है मतलब यह नहीं है - n लगभग हमेशा 2 या 2 है विशेष रूप से जब।
32-बिट इनट्स पर ऑपरेशन पर यह एक बहुत अच्छा बिंदु है। – Skilldrick
अभ्यास में आप सरल संचालन के बारे में सही हैं। हालांकि, एक सिद्धांतवादी के रूप में, मैं कहना चाहता हूं कि आप अभी भी संख्या में बिट्स की संख्या के संदर्भ में जटिलता के बारे में बात कर सकते हैं। 32b के लिए एक ही एल्गोरिदम तरीका ठीक है, लेकिन 64b के लिए धीमा हो जाता है, या जब हम अंततः 1024b या कुछ प्राप्त करते हैं .... फिर, वास्तव में, आप सही हैं, लेकिन यह अभी भी एक दिलचस्प सवाल है। –
* nods *, जैसे ही आप निश्चित-लंबाई इनपुट की सुरक्षित दुनिया से बाहर निकलते हैं, यह बिल्कुल एक दिलचस्प सवाल है। –
स्क्वायर रूट और लॉगरिथम को विभिन्न तरीकों से कार्यान्वित किया जा सकता है, जटिलता को प्रभावित करने (आवश्यक परिशुद्धता के आधार पर)।
यदि वे लुकअप टेबल (और कुछ प्रकार के इंटरपोलेशन) के साथ कार्यान्वित किए जाते हैं, तो स्मृति आवश्यकता वास्तव में अधिक परिशुद्धता की आवश्यकता होती है, लेकिन जटिलता सरणी में मूल्य को देखने और संभावित रूप से इंटरपोलेशन लागू करने की है।
अधिक लोकप्रिय रूप से वे अपनी श्रृंखला परिभाषाओं द्वारा लागू किए जाने लगते हैं। जब तक आप आवश्यक परिशुद्धता तक नहीं पहुंच जाते, तब तक कई राउंड के लिए एक बयान दोबारा शुरू करें या फिर से करें। यहां राउंड की संख्या बहुत अधिक हो सकती है क्योंकि अधिक परिशुद्धता की आवश्यकता होती है, और गणना भी बढ़ी हुई परिशुद्धता से प्रभावित होती है।
+1 दिलचस्प। क्या इसका मतलब है कि एन सटीक बन जाता है? – Skilldrick
@skilldrick आप निश्चित रूप से ऐसा कर सकते हैं। ऐसे एल्गोरिदम हैं जिन्हें उनके इनपुट के बजाए उनके आउटपुट के आकार में मापा जाता है। उनके पास एक नाम है, लेकिन यह शुक्रवार है, इसलिए मुझे इसे याद रखने के लिए परेशान नहीं किया जा सकता है बी-) –
वहाँ एक फूरियर प्रकार एल्गोरिथ्म है कि पूर्णांक गुणा के रूप में अच्छी तरह से करता है (Schonhage-Strassen)
मैंने सोचा था कि पूर्णांक गुणन के लिए सामान्य की तुलना में थोड़ा बेहतर है Strassen एल्गोरिथ्म के एक संस्करण था, लेकिन अब मैं इसके बारे में लगता है कि है, वह एक सीधा के समान होता है ...
अतिरिक्त और घटाव बहुत अधिक है, बस जोड़ और घटाव। डिवीजन और स्क्वायर रूट शायद दिलचस्प हैं ...
ALSO: ध्यान दें कि अब तक सभी ने इंटेगियर अंकगणित के बारे में बात की है। एक बार जब आप तैरते/दोगुनी हो जाते हैं तो सभी दांव बंद हो जाते हैं। फिर आप numerical analysis की दुनिया में आते हैं, और यह अपने पूरे क्षेत्र का है ...
मनमाने ढंग से लंबाई पूर्णांक पर BigInteger पर एक नज़र डालें। इनपुट के आकार के मामले में अब सबकुछ लागत है, जो बिट्स की संख्या है (आमतौर पर O(log K) बिट्स K के लिए बिट्स)। मैं नीचे दिए गए बिट्स की संख्या के लिए N का उपयोग करूंगा।
उदाहरण के लिए, अतिरिक्त और घटाव अब O(N) है। गुणा या तो O(N^2) (बेवकूफ) या O(n (log n)^(2+epsilon) ) एफएफटी के साथ है।
अन्य एल्गोरिदम में "पावर" फ़ंक्शन शामिल है, जो O(N) गुणा लेता है। (अब छोड़कर प्रत्येक गुणा की लागत है!)
और बिगडेसिमल के लिए अतिरिक्त जटिलताएं हैं, जो मनमानी-लंबाई दशमलव समकक्ष हैं, और कुछ अधिक बुनियादी परिचालनों से परे, कुछ चीजें और भी दिलचस्प हैं (विशेष रूप से यदि आप यह जानना चाहते हैं कि आप कितना सटीक चाहते हैं)। आप जावा के कार्यान्वयन पर एक नज़र डाल सकते हैं।
पावर फ़ंक्शन के एक निष्पक्ष कार्यान्वयन के लिए ओ (एन) गुणा की आवश्यकता होती है, लेकिन स्मार्ट कार्यान्वयन ओ (लॉग एन) हैं: http://en.wikipedia।संगठन/विकी/Exponentiation_by_squaring – Juliet
जैसा कि मैंने उल्लेख किया है, 'एन' बिट्स की संख्या है। हालांकि कुछ संख्या 'के' के लिए शक्ति वास्तव में' ओ (लॉग के) 'है। – Larry
बड़ी संख्या में बिट्स के लिए डिवीजन और स्क्वायर जड़ गुणा से कहीं अधिक जटिल नहीं हैं। दोनों परिचालनों के लिए, सादे पुराने न्यूटन पुनरावृत्ति को इस तरह से व्यवस्थित किया जा सकता है कि न्यूटन पुनरावृत्ति में केवल गुणा हो। चूंकि प्रत्येक चरण में सही अंकों की संख्या दोगुनी हो जाती है, इसलिए हम प्रत्येक चरण में गणना की सटीकता को दोगुना कर सकते हैं।
+1 दिलचस्प सवाल। स्पष्टीकरण के लिए, संभवतः वह बिट्स की बढ़ती संख्या के साथ जटिलता का मतलब है। – Tronic
@ पुरानी: क्या आपको बिट्स लगता है? मैट्रिक्स उत्पाद संभावित रूप से मैट्रिक्स के आकार के मामले में होगा ... – Skilldrick
सामुदायिक विकी? –