मैं निम्नलिखित कोड की समय जटिलता पूछना चाहता हूं। क्या ये चालू है)? (क्या Math.pow() ओ (1) की समय जटिलता है?) सामान्य रूप से, Math.pow (ए, बी) में समय जटिलता ओ (बी) या ओ (1) है? अग्रिम में धन्यवाद।जावा Math.pow (ए, बी) समय जटिलता
public void foo(int[] ar) {
int n = ar.length;
int sum = 0;
for(int i = 0; i < n; ++i) {
sum += Math.pow(10,ar[i]);
}
}
@ ब्लिंडी के बारे में वार्तालाप दृष्टिकोण है कि जावा pow लागू करने में सक्षम हो सकता है।
सबसे पहले, सामान्य मामला गुणा दोहराया नहीं जा सकता है। यह सामान्य मामले के लिए काम नहीं करेगा जहां एक्सपोनेंट एक पूर्णांक नहीं है। (! pow के लिए हस्ताक्षर Math.pow(double, double) है)
OpenJDK 8 codebase में, pow के लिए मूल कोड कार्यान्वयन को दो तरह से काम कर सकते हैं:
e_pow.c में पहली कार्यान्वयन घात श्रृंखला का उपयोग करता है। दृष्टिकोण सी टिप्पणी में वर्णित इस प्रकार है:
* Method: Let x = 2 * (1+f)
* 1. Compute and return log2(x) in two pieces:
* log2(x) = w1 + w2,
* where w1 has 53-24 = 29 bit trailing zeros.
* 2. Perform y*log2(x) = n+y' by simulating multi-precision
* arithmetic, where |y'|<=0.5.
* 3. Return x**y = 2**n*exp(y'*log2)
दूसरा कार्यान्वयन w_pow.c में मानक सी पुस्तकालय द्वारा प्रदान की pow समारोह के लिए एक आवरण है। रैपर किनारे के मामलों से संबंधित है।
अब यह संभव है कि मानक सी लाइब्रेरी CPU विशिष्ट गणित निर्देशों का उपयोग करे। यदि ऐसा हुआ, और जेडीके बिल्ड (या रनटाइम) ने दूसरा कार्यान्वयन चुना, तो जावा उन निर्देशों का भी उपयोग करेगा।
लेकिन किसी भी तरह से, मैं किसी भी विशेष केस कोड का कोई निशान नहीं देख सकता जो बार-बार गुणा का उपयोग करता है। आप सुरक्षित रूप से मान सकते हैं कि यह O(1) है।
1 - मैं कैसे जब चयन है/बनाया जा सकता है में delved नहीं किया है।
होगा बार-बार गुणा का उपयोग करना आवश्यक नहीं है। पूर्णांक एक्सपोनेंटिएशन के लिए एक * ओ (लॉग एन) * एल्गोरिदम है। – EJP
@EJP - 1) "आवश्यक" क्या है और वास्तव में क्या होता है वही बात नहीं है। 2) 'int' और' long' के लिए, आप शायद विशेष मामलों के साथ एल्गोरिदम को ट्यून कर सकते हैं ताकि 'ओ' (एन) '' '(' '' की सीमा में 'ओ (लॉग)' से तेज़ हो, जहां आप पूर्णांक अतिप्रवाह नहीं मिलता है। –
@EJP उदा। विशेष मामलों के रूप में एक्स == 0, 1 और 2 और एक्स <0 का इलाज करें। यदि आप बदलावों का उपयोग कर एक्स == 2 केस से निपटते हैं, तो लॉग 3 (2^32) <21; यानी एक्स> = 3 को बार-बार गुणा के 21 या उससे कम राउंड की आवश्यकता होती है। –
आप ओ (1) होने के लिए Math.pow पर विचार कर सकते हैं।
कुछ सीपीयू असेंबलर निर्देश (जावा इसका उपयोग नहीं करता है) से कुछ स्थिर कार्यान्वयन के लिए कुछ संभावित कार्यान्वयन हैं (उदाहरण के लिए) कुछ शर्तों पर टेलर श्रृंखला विस्तार (हालांकि बिल्कुल टेलर कार्यान्वयन नहीं) , कुछ और विशिष्ट एल्गोरिदम हैं)।
यह निश्चित रूप से बार-बार गुणा नहीं करेगा यदि आप इस बारे में चिंतित हैं।
जावा एंबलर निर्देश का उपयोग क्यों नहीं करेगा? कार्यान्वयन मूल है। – chrylis
सी सहित कोई भी नहीं करता है। हार्डवेयर कार्यान्वयन पूरी तरह से मानक अनुरूप नहीं है (NaN हैंडलिंग आईआईआरसी के संबंध में)। हार्डवेयर निर्देशों का उपयोग करने के लिए आपको सी संकलक को स्पष्ट रूप से मजबूर करना होगा (उदाहरण के लिए जीसीसी के लिए 'फास्टमाथ')। – Blindy
@chrylis कोई कंप्यूटर आर्किटेक्चर मुझे पता है कि शक्तियों की गणना के लिए एक निर्देश है। सबसे सरल कार्यान्वयन 'एक्स (बी * लॉग (ए))' –
यदि आप केवल पूर्णांक शक्तियां चाहते हैं, तो अपना स्वयं का पावर फ़ंक्शन लिखना बेहतर है। चूंकि एक int में फिट होने वाली 10 की केवल कुछ शक्तियां हैं, बस एक लुकअप टेबल का उपयोग करें और आप ओ (1) –
@ LưuVĩnhPhúc के साथ अच्छे हैं, लेकिन इसका मतलब है कि आप^बी के लिए बी ऑपरेशन करते हैं। है न?। मूल प्रश्न में, यदि सरणी लंबाई n है, तो सरणी की श्रेणी 0 और n के बीच है, और अधिकतम कम से कम n-1 है। इस प्रकार उपरोक्त कोड में जटिलता ओ (एन^2) होगी? –
मैंने कहां कहा था कि आप शक्तियों के लिए तत्परता से करते हैं? मैंने जो कहा वह एक [लुकअप टेबल] है (https://en.wikipedia.org/wiki/Lookup_table) जैसे 'int pow10 [] = {1, 10, 100, 1000, ... 1000000000};' और प्राप्त करने के लिए 'Math.pow (10, i) 'बस' pow10 [i]' का उपयोग करें। भले ही आप मैन्युअल रूप से गुणा करते हैं, आपको केवल ओ (लॉग एन) की आवश्यकता होती है [स्क्वायरिंग द्वारा एक्सपोनेंटिएशन] (https: //en.wikipedia।संगठन/विकी/Exponentiation_by_squaring) ([एक पूर्णांक आधारित पावर फ़ंक्शन पाउ (int, int) को लागू करने का सबसे प्रभावी तरीका] (http://stackoverflow.com/q/101439/995714)), ओ (एन) ऐसा करने की तरह नहीं यह iteratively –