अधिकतर 4 बिलियन इनट्स

पर एक अनसुलझा सरणी के बीच एक लापता 32 बिट पूर्णांक खोजें यह में वर्णित problem है। मैं लेखक द्वारा अवरुद्ध बाइनरी खोज विधि को समझ नहीं सकता। क्या कोई विस्तार करने में मदद कर सकता है? धन्यवाद।अधिकतर 4 बिलियन इनट्स

संपादित करें: मैं सामान्य रूप से बाइनरी खोज को समझ सकता हूं। मैं समझ नहीं पा रहा हूं कि इस विशेष मामले में बाइनरी खोज कैसे लागू करें। लापता संख्या का निर्धारण कैसे करें किसी सीमा में है या नहीं, ताकि हम एक और चुन सकें। अंग्रेजी मेरी मूल भाषा नहीं है, यही कारण है कि मैं लेखक को अच्छी तरह समझ नहीं सकता। तो, कृपया सादे अंग्रेजी का उपयोग करें :)

संपादित करें: आपके महान उत्तर और टिप्पणियों के लिए धन्यवाद! इस प्रश्न को हल करने से मैं सबसे महत्वपूर्ण सबक लेता हूं बाइनरी खोज न केवल क्रमबद्ध सरणी पर लागू होती है!

स्रोत

2009-10-29 pierrotlefou

आप किस भाग को समझ नहीं सकते? क्या आप विस्तार से समझा सकते हैं? – dirkgently

बाइनरी खोज एक और समस्या का समाधान है। एक अनुरक्षित श्रेणी में एक मूल्य खोजने के लिए उपयुक्त नहीं है। –

आप क्या समझ नहीं सकते? सभी या सिर्फ लेखकों के विवरण पर बाइनरी खोज? –

this web site पर कुछ और जानकारी वहाँ से उद्धरित नहीं है:।।

"यह इस द्विआधारी देखने पर उपयोगी है बीस बिट्स के संदर्भ में खोजें जो प्रत्येक पूर्णांक का प्रतिनिधित्व करते हैं। एल्गोरिदम के पहले पास में हम (अधिकतम) एक मिलियन इनपुट पूर्णांक पढ़ते हैं और उनको एक अग्रणी शून्य बिट के साथ एक टेप में लिखते हैं और जिनके साथ एक दूसरे के टेप में अग्रणी होता है। उन दो टेपों में से एक में अधिकतम 500,000 पूर्णांक हैं, इसलिए हम अगले टेप को वर्तमान इनपुट के रूप में उपयोग करते हैं और जांच प्रक्रिया दोहराते हैं, लेकिन इस बार दूसरी बार। यदि मूल इनपुट टेप में एन तत्व होते हैं, तो पहला पास एन पूर्णांक पढ़ता है, अधिकांश एन/2 पर दूसरा पास, अधिकांश एन/4 पर तीसरा पास, और इसी तरह, इसलिए कुल चलने का समय एन के समान होता है। लापता पूर्णांक टेप पर सॉर्ट करके और फिर स्कैनिंग द्वारा पाया जा सकता है, लेकिन उसे एन लॉग एन के लिए आनुपातिक समय की आवश्यकता होगी। "

जैसा कि आप देख सकते हैं, यह बाइनरी खोज एल्गोरिदम पर भिन्नता है: समस्या को दो टुकड़ों में विभाजित करें और छोटे टुकड़ों में से एक के लिए समस्या का समाधान।

स्रोत

2009-10-29 09:44:20

यदि मुझे सही याद है, 1 + 1/2 + 1/4 .. = योग (1/2^एन) 2 की ओर जाता है। इसलिए ओ (2 एन) –

की जटिलता के रूप में यह दृष्टिकोण सत्य नहीं है। जटिलता वास्तव में ओ (लॉग एन) है। मान लीजिए कि समस्या स्थान 8 है (इसलिए हमें 0,1,2,3,4,5,6,7 रेंज में एक गुम पूर्णांक ढूंढना होगा)। इसके लिए एल्गोरिदम के अधिकतम 3 पास की आवश्यकता होती है। यदि हम समस्या स्थान को 16 तक दोगुना करते हैं, तो हमें एल्गोरिदम के अधिकतम 4 पास की आवश्यकता होती है। तो हालांकि समस्या स्थान 8 से 16 तक दोगुना हो गया है, समस्या को हल करने में लगने वाला समय केवल एक कारक 1.33333 से बढ़ गया है ... यदि हम दोबारा दोगुना हो जाते हैं, तो समस्या को हल करने में लगने वाला समय केवल कारक 1.25 से बढ़ता है । जिसका अर्थ है कि एल्गोरिदम की जटिलता रैखिक नहीं है (इसलिए ओ (2 एन) नहीं)। –

जिस मिनट हमने डेटा के माध्यम से एक पूर्ण पास लिया है, जटिलता ओ (एन) है, इसलिए ओ (लॉग (एन)) सही है। अब ओ (एन) का मतलब है कि कुछ स्थिर, सी है, जैसे कि एल्गोरिदम का चलने का समय सी * एन से ऊपर से घिरा हुआ है, इसलिए ओ (2 एन) बिल्कुल ओ (एन) जैसा ही है। rwwilden, आपकी गलती केवल पास की गणना कर रही थी जब पास का मूल्य भी दोगुना हो जाता है। –

ठीक है, यह एक फाइल है जिसमें एक को छोड़कर सभी 4 बिलियन पूर्णांक शामिल हैं! इस मामले में यह पकड़ है।

जैसे ही आप पूर्णांक की सूची के साथ आगे बढ़ते हैं, योग की गणना करें।
अंत में, योग की गणना करें जैसे फॉर्मूला एन * (एन + 1)/2
(2) पर गणना की गई राशि से राशि (1) पर निकालें। वह गायब पूर्णांक है।

उदाहरण: मान लें कि हमारे पास निम्न अनुक्रम है: 9 3 2 8 4 10 6 1 7 (5 से 5 के बीच 1 से 10)। चूंकि हम अनुक्रमिक रूप से पूर्णांक जोड़ते हैं, हमें 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50 मिलता है। 1 से 10 तक सभी पूर्णांकों का योग 10 * (10 + 1)/2 = 55 होगा इसलिए, गायब पूर्णांक 55 - 50 = 5. QED है

स्रोत

2009-10-29 09:35:32 vbocan

नहीं, यह एक अपरिवर्तित सीमा है। हालांकि, आप सही हैं कि एक से अधिक अंतर हैं (समस्या 4 अरब पूर्णांक पर समस्या कहती है) –

यह लगभग 4 बिलियन पूर्णांक (इसमें कम हो सकती है) में एक फ़ाइल है, जो निश्चित रूप से int32 की पूरी श्रृंखला नहीं है । आपको कम से कम 32 बिट पूर्णांक ढूंढना होगा जो फ़ाइल में नहीं हैं। –

(हटाए गए उत्तर के बारे में खेद है, मैं पहली बार समस्या को भी गलत तरीके से पढ़ता हूं) –

मुझे विश्वास है कि लेखक क्या प्राप्त कर रहा है यह है कि आप पूर्णांक की अपनी वर्तमान श्रृंखला का मध्यबिंदु चुनते हैं, और दो आउटपुट फाइलें तैयार करते हैं। जैसे ही आप अपना इनपुट पढ़ते हैं, मिडपॉइंट के ऊपर सबकुछ एक फ़ाइल में जाता है, और मिडपॉइंट के नीचे सब कुछ दूसरे में जाता है।

एक बार यह समाप्त हो जाने के बाद, आप जो भी फाइलें छोटी हो, उसे चुनते हैं, और फिर अपनी नई रेंज के रूप में [निचला बाउंड, मिडपॉइंट] या (मिडपॉइंट, ऊपरी बाउंड] का उपयोग करके ऑपरेशन दोहराएं, जब तक फ़ाइल और रेंज पर्याप्त न हो बिटमैप पैटर्न के लिए स्विच करने के लिए (या अपने उत्पादन फ़ाइलों में से एक खाली है)

डेमियन

स्रोत

2009-10-29 09:35:34

आप किस मानदंड से ऊपरी आधा और निचला आधा चुनते हैं? चूंकि तत्व अपरिवर्तित हैं। –

@rwwilden - मुझे यकीन नहीं है कि मैं आपकी क्वेरी को समझता हूं? यदि आप पूछ रहे हैं कि आप किस आधे से काम करना जारी रखते हैं, तो मुझे विश्वास है कि मैंने जवाब दिया है (छोटी फ़ाइल, जो समस्या पाठ में इंगित की गई थी) –

@rwwilden - मुझे लगता है कि मैं अस्पष्ट हो सकता था - जब मैं सीमा के बारे में बात कर रहा था, और मध्यबिंदु, मैं संख्यात्मक मानों का जिक्र कर रहा था, न कि इनपुट फ़ाइल में उनकी स्थिति। हम अनिवार्य रूप से एक ही विवरण पोस्ट किया। –

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

यह मूल समस्या पर लागू होता है कि आप कैसे जानते हैं कि पहले कुछ जगहों में कुछ गायब संख्याएं भी हैं।

स्रोत

2009-10-29 09:52:11

यदि आप 1 से एन तक की सीमा में संख्याओं पर विचार करते हैं; उनमें से आधे एन/2 से बड़े हैं और उनमें से आधे एन/2

एन/2 से बड़े वाले एमएसबी को एक सेट में रखना होगा; छोटे के लिए एमएसबी = 0।

विभाजन पूरे सेट MSB के आधार पर जो आप दो सेट दे देंगे: एन/2 की तुलना में छोटे संख्याओं के समूह और की तुलना में एन/2

विभाजन बड़ी संख्या के सेट आकार में छोटे लापता तत्व है ।

अगले चरण में, अगले एमएसबी का उपयोग करें।

तो छोटे सेट एन/2 की तुलना में कम था, उनमें से आधे से भी कम कर रहे हैं N/4 (2 MSB = 0) और दूसरे आधे बड़ा N/4 (2 MSB = 1)
से
यदि छोटा सेट एन/2 से बड़ा था, तो उनमें से आधा एन/2 + एन/4 (2 एमएसबी = 0) से कम है और दूसरा आधा एन/2 + एन/4 (दूसरा एमएसबी = 1)

प्रत्येक दौर खोज स्थान को कम करेगा और यही वह है।

Sum (N/2^i) for 0 <= i < log N gives you O(N)

स्रोत

2009-10-29 10:43:53 ThisIsMeMoony

यह मूल रूप से this question जैसा ही प्रश्न है। ओ (एन) जटिलता प्राप्त करने के लिए पर्याप्त स्मृति मामले के लिए एक ही दृष्टिकोण यहां काम करता है। असल में बस प्रत्येक पूर्णांक को अपने सही स्थान पर रखने का प्रयास करें और देखें कि सही मूल्य क्या नहीं है।

स्रोत

2009-10-29 10:51:27

अधिकतर 4 बिलियन इनट्स

उत्तर

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