1. घर
  2. सवाल और जवाब
  3. जावा 7 के बिगइंटर पर कौन सी जटिलताएं हैं?

जावा 7 के बिगइंटर पर कौन सी जटिलताएं हैं?

2010-01-28 9 views
6

वर्तमान में BigInteger में multiply, divide और pow के तरीके क्या जटिलता हैं? दस्तावेज में कम्प्यूटेशनल जटिलता का कोई उल्लेख नहीं है (न ही कहीं और)।जावा 7 के बिगइंटर पर कौन सी जटिलताएं हैं?

स्रोत

2010-01-28 Anonymous

+0

आप स्रोत कोड की जांच कर सकता है। – uckelman

+0

असल में मैंने पहले ही कोशिश की है। लेकिन बहुत सारे ज्ञान के बिना विश्लेषण करना मुश्किल लगता है। मुझे उम्मीद है कि स्टैक ओवरफ्लो पढ़ने वाला कोई व्यक्ति उस ज्ञान को प्राप्त करता है। शायद यह बहुत आशावादी है? –

+0

क्या कोई विशिष्ट कारण है कि आप जावा 7 का उल्लेख क्यों करते हैं? जावा 1.1 के बाद से 'BigInteger' मौजूद है। –

उत्तर

3

आप (JDK के साथ प्रदान की) BigInteger के लिए कोड को देखें, तो मुझे ऐसा लगता है कि multiply(..) है O (n^2) (वास्तव में विधि multiplyToLen(..) है)। अन्य तरीकों के लिए कोड थोड़ा अधिक जटिल है, लेकिन आप स्वयं को देख सकते हैं।

नोट: इस मैं यह जावा 7.

स्रोत

2010-01-28 11:42:04 Bozho

+3

गुणा की कई जटिलताओं हैं: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations ... क्या आप O (n^2) ओ (एन^1.585) या ओ (एन^1.465) के अलावा बता सकते हैं? – Joey

+1

मेरा मानना ​​है कि जावा 7 में बदलाव हुए हैं। मुझे उन विवरणों को याद नहीं है जिन्हें मैंने खोजा था, लेकिन वे दुर्लभ थे। –

+0

रोस्सेल: गुणा के लिए _exist_ अन्य एल्गोरिदम, लेकिन जावा 6 उनका उपयोग नहीं करता है। बड़ी संख्या में गुणा करते समय आप निश्चित रूप से स्कूलबुक एल्गोरिदम और करात्सुबा गुणा के बीच का अंतर देखेंगे। जब तक आप संख्याओं के साथ प्राथमिक स्मृति भर नहीं रहे हैं, तब तक अन्य लोग कूदते हैं। – Charles

2

में मतभेद नहीं होगा मान यह उपाय जावा 6. के लिए है। रैखिक रूप से बढ़ते संचालन के साथ संचालन करें और आरेख पर समय खींचें। मान्य बेंचमार्क परिणाम प्राप्त करने के लिए JVM (कई रन) को गर्म करना न भूलें।

यदि संचालन रैखिक ओ (एन), क्वाड्रैटिक ओ (एन^2), बहुपद या घातीय स्पष्ट होना चाहिए।

संपादित करें: जबकि आप एल्गोरिदम सैद्धांतिक सीमाएं दे सकते हैं, वे अभ्यास में इतना उपयोगी नहीं हो सकते हैं। सबसे पहले, जटिलता कारक नहीं देती है। कुछ रैखिक या subquadratic एल्गोरिदम बस उपयोगी नहीं हैं क्योंकि वे इतना समय और संसाधन खा रहे हैं कि वे हाथ की समस्या के लिए पर्याप्त नहीं हैं (उदाहरण के लिए कॉपरस्मिथ-विनोग्रैड मैट्रिक्स गुणा)। फिर आपके गणना में सभी क्लुज हो सकते हैं जिन्हें आप केवल प्रयोग द्वारा ही पहचान सकते हैं। वहां एल्गोरिदम तैयार कर रहे हैं जो समस्या को हल करने के लिए कुछ भी नहीं करते हैं बल्कि वास्तविक सॉल्वर (मैट्रिक्स कंडीशनिंग) को गति देने के लिए कुछ भी नहीं करते हैं। उप-कार्यान्वयन कार्यान्वयन हैं। लंबी लंबाई के साथ, आपकी गति नाटकीय रूप से गिर सकती है (कैश गायब, स्मृति चलती आदि)। तो व्यावहारिक उद्देश्यों के लिए, मैं प्रयोग करने की सलाह देता हूं।

सर्वोत्तम बात इनपुट की लंबाई और समय की तुलना करने के लिए सबसे अच्छी बात है। और हाँ, आप पता लगाएं कि क्या एल्गोरिदम में^^ 1.5 या n^1.8 जटिलता है। बस इनपुट की लंबाई चौगुनी करें और आपको 2 के बजाय 1.5 के लिए केवल आधे समय की आवश्यकता है। यदि आप लंबाई 256 गुना गुणा करते हैं तो आपको 1.8 के लिए लगभग आधा समय मिलता है।

स्रोत

2010-01-28 11:42:17

+0

यह काम कर सकता है। मुझे एन के बड़े मूल्यों की जांच करने की आवश्यकता होगी। अगर मैंने दो एन-बिट बिगइंटर (टी_0) और फिर दो 2 एन-बिट बिगइंटर (टी_1) गुणा करने के लिए समय मापा। तो मैं जटिलता ओ (एन^(लॉग 2 (टी_1/टी_0)) होने की उम्मीद कर सकता हूं)। आम तौर पर मैं अनुभवजन्य तरीकों की थोड़ी संदिग्ध हूं हालांकि (संभवतः अनुचित)। –

+0

हालांकि, यह लेने के लिए एक कठिन दृष्टिकोण है। _A prei_, यह सोचने का कोई कारण नहीं है कि एल्गोरिदम के संयोजन के बजाय एक एकल एल्गोरिदम का उपयोग किया जाता है। इस प्रकार 10 अंकों से 1000 अंकों तक स्केलिंग 1000 अंकों से 3000 अंकों तक स्केलिंग से भिन्न हो सकती है। – Charles

1

एक नया "बेहतर" बिगइंटर वर्ग है जिसका उपयोग रूढ़िवाद और उपयोगी प्रतिगमन परीक्षण (विशाल डेटा सेट) की कमी के लिए सूर्य जेडीके द्वारा नहीं किया जा रहा है। जिस व्यक्ति ने बेहतर एल्गोरिदम किया था, उसने टिप्पणियों में पुराने बिगइन्टर पर चर्चा की हो सकती है।

यहां आपको http://futureboy.us/temp/BigInteger.java

स्रोत

2010-03-16 01:37:33 i30817

संबंधित मुद्दे

 संबंधित मुद्दे