एक सरणी में कम से कम समय के साथ मंझला खोजने के

Question

मैं एक सरणी अब a = { 1,4,5,6,2,23,4,2}; कहते हैं कि मैं 2 से 6 (विषम कुल शब्द) के लिए सरणी स्थिति की औसत खोजने के लिए देता है, तो मैं क्या किया है, मैं a[1]a[5] को ले लिया है arr[0] से arr[4] में मैंने इसे क्रमबद्ध किया है और arr[2] औसत के रूप में लिखा है।

लेकिन यहां हर बार जब मैं एक सरणी से दूसरे में मूल्य इनपुट कर रहा हूं, तो मेरे प्रारंभिक सरणी के मान समान रहते हैं। दूसरी बात मैंने हल की है, इसलिए यह प्रक्रिया बहुत अधिक **time** ले रही है। तो मैं जानना चाहता हूं कि less my computation time पर अलग-अलग तरीके से मैं इसे कैसे कर सकता हूं।

कोई भी वेबसाइट, समझने के लिए सामग्री, क्या और कैसे करें?

Answer 1

आप एक ही सरणी पर कई प्रश्नों कर रहे हैं तो आप एक सेगमेंट ट्री इस्तेमाल कर सकते हैं। वे आमतौर पर न्यूनतम/अधिकतम और रेंज योग क्वेरी करने के लिए उपयोग किए जाते हैं लेकिन आप इसे रेंज मध्यस्थ करने के लिए बदल सकते हैं।

एन अंतराल वाले सेट के लिए एक सेगमेंट पेड़ ओ (एन लॉग एन) स्टोरेज का उपयोग करता है और ओ (एन लॉग एन) समय में बनाया जा सकता है। ओ (लॉग एन) में एक रेंज क्वेरी किया जा सकता है। सीमा खंड पेड़ में मध्यिका की

उदाहरण:

    [5] 
     [3]      [7] 
[1,2]  [4]   [6]   [8] 
1  2  3  4  5  6  7  8 

सूचकांकों नोड के अंतर्गत आने वाले:

    [4] 
     [2]      [6] 
[0,1]  [3]   [5]   [7] 
0  1  2  3  4  5  6  7 

आप नीचे से ऊपर खंड पेड़ (नीचे ऊपर से अद्यतन) का निर्माण

4-6 के रेंज इंडेक्स के लिए औसत के लिए एक प्रश्न मूल्यों के इस पथ से नीचे जाएगा:

    [4] 
          [5] 
0  1  2  3  4  5  6  7 

औसत के लिए खोज करना, आप क्वेरी (3) में कुल तत्वों की संख्या जानते हैं और उस श्रेणी में औसत दूसरे तत्व (सूचकांक 5) होगा। तो आप अनिवार्य रूप से पहले नोड की खोज कर रहे हैं जिसमें वह इंडेक्स है जो मानों के साथ नोड [1,2] (सूचकांक 0,1) है।

श्रेणी 3-6 के औसत की खोज करना थोड़ा अधिक जटिल है क्योंकि आपको दो सूचकांक (4,5) की खोज करना है जो एक ही नोड में झूठ बोलते हैं।

    [4] 
           [6] 
          [5] 
0  1  2  3  4  5  6  7 

Segment tree

Range minimum query on Segment Tree

Answer 2

ओ (एन) समय में सॉर्ट किए बिना औसत ढूंढना संभव है; एल्गोरिदम जो इसे करते हैं उन्हें selection algorithms कहा जाता है।

Answer 3

9 तत्वों से कम की एक सरणी के औसत को खोजने के लिए, मुझे लगता है कि सम्मिलन क्रम जैसे सॉर्ट एल्गोरिदम का उपयोग करना सबसे कुशल है। जटिलता खराब है, लेकिन k की वजह से इस तरह की एक छोटी सरणी के लिए क्विकॉर्ट जैसे बेहतर एल्गोरिदम की जटिलता में, सम्मिलन क्रम बहुत ही कुशल है। अपना खुद का बेंचमार्क करें लेकिन मैं बता सकता हूं कि आपके पास शेल सॉर्ट या क्विकॉर्ट के मुकाबले सम्मिलन प्रकार के साथ बेहतर परिणाम होंगे।

Answer 4

उपयोग std::nth_element<algorithm> से जो हे (एन) है:

nth_element(a, a + size/2, a + size); 
median = a[size/2]; 

Answer 5

मुझे लगता है कि सबसे अच्छा तरीका है k- वां एक सरणी के सबसे बड़े तत्व गिनती की माध्यिकाओं एल्गोरिथ्म की औसत उपयोग करने के लिए है। आप यहां एल्गोरिदम का समग्र विचार पा सकते हैं: Median of Medians in Java, विकिपीडिया पर: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm या बस इंटरनेट ब्राउज़ करें। कार्यान्वयन के दौरान कुछ सामान्य सुधार किए जा सकते हैं (विशेष सरणी के औसत को चुनते समय सॉर्टिंग से बचें)। हालांकि, ध्यान दें कि 50 से कम तत्वों की एक सरणी के लिए औसत एल्गोरिदम के औसत से सम्मिलन प्रकार का उपयोग करने के लिए यह अधिक कुशल है।