एल्गोरिदम किसी दिए गए स्ट्रिंग

Question

में रिक्त स्थान के सबसे लंबे अनुक्रम के दसवें हिस्से को खोजने के लिए एक दिए गए स्ट्रिंग में रिक्त स्थान के सबसे लंबे अनुक्रम की लंबाई को खोजने के लिए एक एल्गोरिदम खोजना संभव है जितना संभव हो उतना वर्ण?

संकेत: रिक्त स्थान के अनुक्रम की लंबाई बढ़ने के साथ आपका प्रोग्राम तेज़ी से बढ़ना चाहिए।

मैं समाधान जो हे (एन) है .. लेकिन अधिक इष्टतम समाधान

Answer 1

की तलाश में लेकिन सबसे खराब स्थिति में (जब सभी पात्रों खाली कर रहे हैं) आप हर चरित्र की जांच करने के लिए है। तो यह जटिलता में ओ (एन) से बेहतर नहीं हो सकता है।

तर्क: मान लें कि पूरी स्ट्रिंग खाली है, आपने एन अक्षरों की जांच नहीं की है और आपके एल्गोरिदम n आउटपुट करते हैं। फिर यदि कोई गैर-जांच चरित्र खाली नहीं है, तो आपका जवाब गलत होगा। तो इस विशेष इनपुट के लिए आपको पूरी स्ट्रिंग की जांच करनी होगी।

Answer 2

आप ऐसे समाधान को नहीं ढूंढ पाएंगे जो ओ (एन) की तुलना में एक छोटी जटिलता है क्योंकि आपको इनपुट स्ट्रिंग के साथ सबसे खराब मामले में हर चरित्र को पार करने की आवश्यकता है जिसमें अधिकतम 0 या 1 लगातार सफेद जगह है, या पूरी तरह से सफेद जगह है।

हालांकि आप कुछ अनुकूलन कर सकते हैं, लेकिन इसे अभी भी ओ (एन) माना जाएगा।

उदाहरण के लिए:

Let एम अब तक के रूप में आप अपनी सूची के माध्यम से जाना वर्तमान सबसे लंबे समय तक मैच हो। यह भी मान लें कि आप ओ (1) में इनपुट तत्वों तक पहुंच सकते हैं, उदाहरण के लिए आपके पास इनपुट के रूप में एक सरणी है।

जब आप एक गैर-व्हाइटस्पेस देखते हैं तो आप एम तत्वों को छोड़ सकते हैं यदि current + M गैर व्हाइटस्पेस है। निश्चित रूप से एम से अधिक लंबी जगह नहीं हो सकती है।

और जब आप एक व्हाइटस्पेस चरित्र देखते हैं, तो current + M-1 सफेद जगह नहीं है, आपको पता है कि आपके पास सबसे लंबा रन नहीं है जब आप उस मामले में भी जा सकते हैं।

Answer 3

आप जो भी करते हैं, सबसे खराब मामला हमेशा ओ (एन) होगा - यदि वे रिक्त स्थान स्ट्रिंग के अंतिम भाग पर हैं ... (या स्ट्रिंग का अंतिम "चेक" भाग)।

Answer 4

स्पष्ट विचार: आप के + 1 स्थानों (जहां के वर्तमान सबसे लंबा अंतरिक्ष अनुक्रम है) द्वारा कूद सकते हैं और यदि आपको कोई स्थान मिल जाए तो वापस स्कैन करें।

इस तरह आपके पास कुछ (एन + एन/एम)/2 = एन (एम + 1)/2 एम पदों की जांच की गई है।

संपादित करें:
एक और विचार बाइनरी खोज को लागू करना होगा। यह निम्नानुसार है: दिए गए के के लिए आप एक प्रक्रिया करते हैं जो जांचता है कि लंबाई> = k के साथ रिक्त स्थान का अनुक्रम है या नहीं। यह ओ (एन/के) चरणों में हासिल किया जा सकता है। फिर, आप द्विआधारी खोज के साथ अधिकतम के खोजने का प्रयास करें।

संपादित करें:
फलस्वरूप खोज के दौरान, आप ज्ञान का उपयोग कर सकते हैं कि कुछ लंबाई कश्मीर पहले से ही मौजूद के अनुक्रम, और शुरू से ही कश्मीर पर लंघन शुरू करते हैं।

Answer 5

सबसे खराब मामले में O(N) से तेज़ी से बनाने का कोई तरीका नहीं है। हालांकि, 0-आधारित अनुक्रमण मानते हुए, कुछ अनुकूलन यहां दिए गए हैं।

1. आप पहले से ही L कारतूस की एक पूरी अनुक्रम है, और L अपने स्ट्रिंग के आधे आकार के रूप में कम से कम के रूप में बड़ा है (पूरा द्वारा मैं एक दृश्य है कि एक बड़ा दृश्य के किसी परिणाम नहीं है मतलब है), तो आप रुक सकते हैं।
2. यदि आपके पास L रिक्त स्थान का एक पूर्ण अनुक्रम है, तो एक बार जब आप स्थिति i पर कोई स्थान दबाते हैं तो जांच करें कि i + L स्थिति में वर्ण भी एक स्थान है या नहीं। यदि ऐसा है, तो i स्थिति से स्कैनिंग जारी रखें क्योंकि आपको एक बड़ा अनुक्रम मिल सकता है - हालांकि, यदि आप i + L स्थिति तक एक गैर-स्थान का सामना करते हैं, तो आप सीधे i + L + 1 पर जा सकते हैं। यदि यह कोई स्थान नहीं है, तो i से शुरू होने वाला एक बड़ा अनुक्रम बनाने का कोई तरीका नहीं है, इसलिए आगे i + L + 1 से आगे स्कैन करें।
3. आप लंबाई L के रिक्त स्थान की एक पूरी अनुक्रम है, और आप स्थिति i पर रहे हैं और आप k पदों जांच करने के लिए छोड़ दिया है, और k <= L हैं, तो आप अपनी खोज को बंद कर सकते हैं, स्पष्ट रूप से कोई रास्ता नहीं आप कर सकेंगे के रूप में अब और कुछ बेहतर पाएं।

यह साबित करने के लिए कि आप इसे O(N) से अधिक तेज़ नहीं बना सकते हैं, उस स्ट्रिंग पर विचार करें जिसमें कोई रिक्त स्थान नहीं है। आपको प्रत्येक चरित्र को एक बार एक्सेस करना होगा, इसलिए यह O(N) है। एक स्ट्रिंग के साथ ही जिसमें रिक्त स्थान के अलावा कुछ भी नहीं है।