पूर्णांकों की एक सरणी पर विचार करें। एक जोड़ी (i, j) को A if i <j और A [i]> A [j] में व्युत्क्रम कहा जाता है।
सरणी में प्रत्येक स्थिति "i" के लिए दो संभावित उम्मीदवार हैं: एक [i] संभाव्यता p [i] और एक [i] + x जिसमें प्रायिकता 1-p [i]।
अब मुझे अपेक्षित संख्या में व्युत्क्रमों की गणना करनी है। हर इंडेक्स i और पूर्णांक x के लिए [i] और p [i] दिया जाता है।
मुझे पता है कि ओ (एन ^ 2) दृष्टिकोण (प्रत्येक कानूनी जाँच करें)संभव जोड़ी)। इसके अलावा, मैं एक सरणी में व्युत्क्रमों की संख्या की गणना करने के लिए O (nlogn) दृष्टिकोण को जानता हूं जिसमें सभी तत्व 100% संभावना के साथ पूर्व निर्धारित हैं। यह मर्ज सॉर्ट को संशोधित करके किया जाता है।
मैं n वर्ग से बेहतर दृष्टिकोण जानना चाहता हूं। कृपया मुझे बताओ।
उत्तर:
जवाब के लिए 2 № 1यह उलटी गिनती के लिए मानक मर्ज-सॉर्ट आधारित एल्गोरिथ्म के लिए एक सरल संशोधन के साथ किया जा सकता है, जहां हम प्रत्येक मूल्य के लिए एक वजन असाइन करते हैं और योग की गणना करते हैं। W[i]*W[j] के लिये i<j, A[i]>A[j] (जब प्रत्येक वजन 1 होता है, तो हम सामान्य गिनती प्राप्त करते हैं)।बाएं सरणी में शेष तत्वों की संख्या की गिनती में जोड़ने के बजाय, हम इन तत्वों के वजन को जोड़ते हैं जो हम सही प्रसंस्करण में तत्व के वजन से गुणा करते हैं।
इस एल्गोरिथ्म का उपयोग करने के लिए posed समस्या को हल करने के लिए,बस दो बार आकार की एक सरणी बनाएं, जहां मूल सरणी में प्रत्येक तत्व को दो तत्वों (क्रमबद्ध क्रम में) द्वारा प्रतिस्थापित किया जाता है, संभावनाओं द्वारा दिए गए भार के साथ।
जवाब के लिए 0 № 2
मैंने यह समझाते हुए एक टिप्पणी छोड़ दी, लेकिन आप कर सकते हैंयदि आप गणित का थोड़ा सा उपयोग करते हैं तो इसका O (1) गणना करें। मैं आपको काम छोड़ दूँगा, लेकिन, मेरी गणना से, एन पूर्णांकों की एक सरणी में व्युत्क्रमों की अपेक्षित संख्या है ((n ^ 2) - (n)) / 4. कोष्ठक की बहुतायत के लिए क्षमा करें, मुझे बस चाहिए था यह सुनिश्चित करने के लिए कि मैं पूरी तरह से स्पष्ट हूं। यदि आप चाहते हैं तो मैं काम को पोस्ट कर सकता हूं, लेकिन मुझे लगा कि मैं इसे छोड़ देता हूं अगर आपको सिर्फ जवाब चाहिए।
इसलिए, मेरी टिप्पणी के बावजूद, मुझे गलत याद आया। यह नहीं है lg (n)।