एक अवर्गीकृत पूर्णांक सरणी को देखते हुए है खोजने के लिए यह संभव है, और सरणी में संख्या पर कोई मान्यताओं बनाने के बिना:
यह संभव दो नंबर जिसका पता लगाने के लिए है अंतर ओ (एन) समय में न्यूनतम है?दो नंबर जिसका अंतर में हे (एन) न्यूनतम समय
संपादित करें: दो संख्याओं के बीच अंतर क, ख abs(a-b)
सूची में सबसे छोटा और सबसे बड़ा तत्व खोजें। अंतर सबसे छोटा सबसे छोटा होगा।
यदि आप nonnegative अंतर की तलाश में हैं, तो यह निश्चित रूप से कम से कम उतना कठिन है जितना कि सरणी में दो समान तत्व हैं। इसे element uniqueness problem कहा जाता है और बिना किसी अतिरिक्त धारणा के (जैसे पूर्णांक के आकार को सीमित करने, तुलना की तुलना में अन्य परिचालनों की अनुमति) के लिए> = n लॉग n समय की आवश्यकता होती है। यह closest pair of points खोजने का 1-आयामी मामला है।
मुझे लगता है कि एक सेट के लिए [5, 6, 1, 10] वे 1, नहीं -9 की तलाश में हैं। –
@ कैथी: फिर उन्हें लिखा जाना चाहिए "दो * विशिष्ट * पूर्णांक खोजें जिनके * अंतर का मॉड्यूलस * न्यूनतम है"। चेतावनी विनिर्देशक :) –
+1 * अंतर * की सामान्य धारणाओं के बाहर सोचने के लिए +1। –
नहीं के रूप में, संख्या/आदेश के बारे में मान्यताओं बनाने के बिना नहीं परिभाषित किया गया है।
हालांकि एक क्रमबद्ध सूची दी जा सकती है।
मुझे नहीं लगता कि आप इसे ओ (एन) में कर सकते हैं। सबसे अच्छा मैं अपने सिर के ऊपर से आ सकता हूं उन्हें सॉर्ट करना है (जो ओ (एन * लॉग एन) है) और क्रमबद्ध सूची में आसन्न जोड़े का न्यूनतम अंतर ढूंढें (जो एक और ओ (एन) जोड़ता है)।
मैं वही सोच रहा हूं लेकिन @ माइकल टोड का कहना है कि आप इसे ओ ओ (एन) कर सकते हैं इसलिए मैं उत्सुकता से यह देखने का इंतजार कर रहा हूं कि वह –
@non sequitor पोस्ट करता है: उम्मीद है कि वह जल्द ही हमारे पास वापस आ जाएगा। मुझे गलत सिद्ध होने में खुशी है। :) –
मुझे लगता है कि आप करीब हैं - एक रेडिक्सपोर्ट आपको ओ (एन) सॉर्टिंग समय देगा, फिर ओ (एन) आसन्न जोड़ी पुनरावृत्ति के लिए। – fbrereto
सबसे अच्छा मैं सोच सकता हूं कि counting sort सरणी (संभवतः बराबर मानों को जोड़ती है) और फिर क्रमबद्ध तुलना करें - बिन सॉर्ट ओ (एन + एम) (एम विशिष्ट मानों की संख्या है)। हालांकि, इसकी भारी स्मृति आवश्यकता है। बाल्टी या रेडिक्स प्रकार के कुछ रूप समय में मध्यवर्ती और अंतरिक्ष में अधिक कुशल होंगे।
आपको शायद रेडिक्स सॉर्ट का उपयोग करना होगा, नहीं? आपको संख्याओं की संभावित सीमा नहीं दी गई है, इसलिए गिनती सॉर्ट विंडो से तुरंत बाहर हो जाएगी। –
रेंज ढूंढना एक ओ (एन) ऑपरेशन (न्यूनतम, अधिकतम) है। –
हां, लेकिन इस मामले में सीमा मनमाने ढंग से बड़ी हो सकती है।उनकी प्रतिक्रिया पर बिल द लिज़र की टिप्पणी देखें। – PeterAllenWebb
क्रमबद्ध radixsort साथ सूची (जो हे (एन) पूर्णांकों के लिए है), तो पुनरावृति और अब तक का सबसे छोटा दूरी पर नज़र रखें।
(मुझे लगता है अपने पूर्णांक एक निश्चित बिट प्रकार है। वे मनमाने ढंग से बड़े गणितीय पूर्णांकों पकड़ कर सकते हैं, radixsort O (n n लॉग इन करें) के रूप में अच्छी तरह से हो जाएगा।)
मुझे नहीं लगता कि आपको गारंटी है कि यहां स्थिर है। क्या होगा अगर के = एन? –
रैडिक्स सॉर्ट केवल ओ (एन) है क्योंकि यह एल्गोरिदम में सीमा बनाता है। यदि आप सामान्य int मानों को क्रमबद्ध कर रहे हैं जो अद्वितीय होने की गारंटी है, तो यह वास्तव में ओ (1) है। यदि आप मनमाने ढंग से बड़ी संख्याओं को क्रमबद्ध कर रहे हैं, तो यह ओ (एन) नहीं है। –
आप सही हैं, पूर्णांक एक चर-लंबाई डेटाटाइप का संदर्भ ले सकता है। मैंने अपना जवाब उस स्थिति में संपादित किया है जो धारणा है। – meriton
यह seems असीम सॉर्ट करने के लिए संभव हो सकता है ओ (एन * एसक्यूआरटी (लॉग (लॉग (एन)) में पूर्णांक का सेट) समय। क्रमबद्ध करने के बाद रैखिक समय में न्यूनतम अंतर खोजने के लिए यह मामूली है।
लेकिन मैं किसी भी एल्गोरिदम के बारे में नहीं सोच सकता इसे इससे तेज बनाएं।
मुझे लगता है कि उत्तर नहीं है और सबूत इस सबूत के समान है कि आप एन एलजी एन से तेज़ी से सॉर्ट नहीं कर सकते: आपके पास है सभी तत्वों की तुलना करने के लिए, यानी तुलनात्मक पेड़ बनाएं, जो ओमेगा (एन एलजी एन) एल्गोरिदम का तात्पर्य है।
संपादित करें। ठीक है, अगर आप वास्तव में बहस करना चाहते हैं, तो सवाल यह नहीं कहता कि यह एक ट्यूरिंग मशीन होनी चाहिए या नहीं। क्वांटम कंप्यूटर के साथ, आप इसे रैखिक समय में कर सकते हैं :)
आपको सभी तत्वों की तुलना क्यों करना है? जाहिर है आपको उन्हें देखने की जरूरत है, लेकिन क्यों * तुलना करें *? – meriton
ठीक है, चलो इसे "संख्याओं को देखते हुए" कहते हैं, वैसे भी, एक तुलना पेड़ होगा। –
आप अभी भी इस समस्या के लिए हर अच्छा एल्गोरिदम मानते हैं तुलनात्मक पेड़ों की तुलना और तुलना करेंगे। चूंकि आप इस धारणा को औचित्य नहीं देते हैं, इसलिए आपका सबूत अपूर्ण है। – meriton
मुझे लगता है कि यह संभव है। रहस्य यह है कि आपको वास्तव में सूची को क्रमबद्ध नहीं करना है, आपको बस एक संख्या बनाने की जरूरत है कि कौन से नंबर मौजूद हैं। यह एक एल्गोरिदमिक परिप्रेक्ष्य से "धारणा बनाने" के रूप में गिना जा सकता है, लेकिन व्यावहारिक परिप्रेक्ष्य से नहीं। हम जानते हैं कि इनट्स एक मिनट और अधिकतम से बंधे होते हैं।
तो, समावेशी INT_MAX करने के लिए 2 बिट तत्वों, की एक सरणी 1 प्रत्येक के लिए जोड़ी INT_MIN से int बनाने के लिए, संख्या की पूरी सूची के माध्यम से 00
पुनरावृत्ति करने के लिए उन सभी को निर्धारित किया है। सूची में प्रत्येक नंबर के लिए, यदि संबंधित 2 बिट्स 00 हैं तो उन्हें 01 पर सेट करें। यदि वे 01 हैं तो उन्हें 10 पर सेट करें। अन्यथा अनदेखा करें। यह स्पष्ट रूप से ओ (एन) है।
अगला, यदि 2 बिट्स में से कोई भी 10 पर सेट है, तो यह आपका उत्तर है। न्यूनतम दूरी 0 है क्योंकि सूची में दोहराया गया नंबर है। यदि नहीं, तो सूची के माध्यम से स्कैन करें और न्यूनतम दूरी खोजें। बहुत से लोगों ने पहले ही बताया है कि इसके लिए सरल ओ (एन) एल्गोरिदम हैं।
तो ओ (एन) + ओ (एन) = ओ (एन)।
संपादित करें: टिप्पणियों का जवाब दें।
दिलचस्प अंक। मुझे लगता है कि आप सूची के न्यूनतम/अधिकतम को ढूंढकर और डेटा को पकड़ने के लिए न्यूनतम से अधिकतम तक की एक स्पैस सरणी का उपयोग करके किसी भी धारणा के बिना एक ही परिणाम प्राप्त कर सकते हैं। INT_MIN/MAX धारणा, अंतरिक्ष जटिलता और सरणी स्कैनिंग की ओ (एम) समय जटिलता का ख्याल रखता है।
कौन कहता है कि इसे परिमित आकार वाले सिस्टम वाले सिस्टम में कार्यान्वित किया जा रहा है? –
यदि आपका एल्गोरिदम इंट्स पर एक मिनट और अधिकतम से घिरा हुआ है, तो यह वास्तव में ओ (1) है। एन पर अधिकतम दिया गया है, ऑपरेशन में एक निश्चित समय लगेगा। –
आपकी सरणी की लंबाई ओ (एन) में नहीं है, लेकिन आप मानते हैं कि इसे 00-तत्वों के साथ प्रारंभ किया गया है। इसके अलावा, आप सबसे छोटी दूरी खोजने के लिए * सूची के माध्यम से कैसे स्कैन करते हैं? – meriton
क्या आप अपना रास्ता धोखा दे सकते हैं और उसी दो पूर्णांक की खोज कर सकते हैं, क्योंकि उनका अंतर न्यूनतम होगा? –
@aforloney - मुझे लगता है कि "सरणी में संख्याओं पर कोई धारणा किए बिना" आवश्यकता उस पर शासन करेगी। –
@aflorloney: न्यूनतम की आपकी परिभाषा पर निर्भर करता है। (10 - 10)> (2 - 3)। – Juliet