समांतर

Question

में एक औसत खोजें यदि आपके पास बड़ी संख्या में संख्याएं और एक सौ कंप्यूटर हैं, आप संख्याओं के औसत कैसे पाएंगे?

Answer 1

चयन एल्गोरिदम का उपयोग करें।

1. संख्या की सरणी को 100 विभाजन में विभाजित करें।
2. प्रत्येक प्रोसेसर दो समूहों के लिए सरणी विभाजित करने के लिए सामान्य धुरी का उपयोग करना चाहिए (बाएं/सही)
3. तो प्रत्येक प्रोसेसर नेता
4. नेता की गणना करना चाहिए जो समूह छोटा होता है करने के लिए उन 2 समूहों के आकार भेजना चाहिए और उन समूहों में से किसी एक से छुटकारा पाने के लिए एक संदेश प्रसारित करें।
5. चरण 2 पर जब तक आप यह हे (एन) के asymptotic क्रम, प्रत्येक प्रोसेसर संख्या विभाजित करना चाहिए बनाने के लिए मंझला

इस समाधान हे (एन) के एक औसत क्रम है खोजने के वापस जाने के लिए 5 तत्वों के समूहों को प्रत्येक समूह के औसत (सम्मिलन क्रम का उपयोग करके) प्राप्त करें और उन medians को नेता को वापस भेज दें, नेता उन median के मध्य का चयन करेगा (एक ही algo का उपयोग कर) और पिवट

होगा

विकी आलेख पढ़ें - http://en.wikipedia.org/wiki/Selection_algorithm