सरणी में प्रत्येक आइटम से पहले कितने तत्व छोटे होते हैं

Question

सरणी में i प्रत्येक स्थिति के लिए N < 10 000 तत्वों की एक श्रृंखला को देखते हुए, (सबसे कुशल तरीके से) कितनी लगातार तत्व इसके बाएं से शुरू होते हैं (यानी स्थिति से i-1 से 0) array[i] के छोटे या बराबर हैं।

यहाँ एक उदाहरण है:

Array: 4 3 6 1 1 2 8 5 9 
Res: 0 0 2 0 1 2 6 0 8 
(pos 0 (element 4) -> 0 consecutive elements before it, 
    pos 1 (element 3) -> 0 consecutive elements before it smaller than 3 (4>3) 
    pos 2 (element 6) -> 2 consecutive elements before it smaller than 6 (4,3) 
    and so on.. 
) 

मैं इसे एक गतिशील प्रोग्रामिंग सवाल है, क्योंकि यह समस्या 'सबसे कारगर तरीका' में कहते हैं और घोल में वहाँ एक O(n) समाधान का कहना है ग्रहण करेंगे।

O(n^2) समाधान सरल है, दो loops, तत्वों की गिनती।

इस बारे में मेरा विचार है कि 0(n) कैसे। एक ग्रहण करेंगे:

for (int i = 1; i < array.Length; i++) { 
    if (array[i-1] > array[i]) 
    { 
     c [i] = 0; 
    } 
    else { 
     c [i] = c [i - 1] + MAGIC_FORMULA; 
    } 
} 

जाहिर है, अगर मैं अगले एक से अधिक एक तत्व मिल जाए, परिणाम स्पष्ट रूप से (बाईं ओर कोई संख्या यह की तुलना में छोटे) 0 है। लेकिन पिछले परिणाम मुझे क्या बताता है ताकि मैं गतिशील प्रोग्रामिंग का उपयोग कर सकूं? मुझे उस मामले के लिए कोई पुनरावृत्ति नहीं मिल रही है। साथ ही, पूरे समाधान के लिए O(n) होने के लिए, उस सूत्र को O(1) में प्राप्य होना होगा, है ना? हैशसेट का उपयोग करने के बारे में सोचा, लेकिन इसे समझ नहीं सका। कडेन के एल्गोरिदम के कुछ संशोधित संस्करण का उपयोग करने के बारे में सोचा, लेकिन कोई भाग्य नहीं।

मैं O(n) समाधान को समझने के लिए मर रहा हूं। मैंने पूरे दिन O(n) समाधान के बारे में सोचा है और मैं वास्तव में अटक गया हूं।

मैं मूल नहीं हूं इसलिए इस प्रश्न को बेहतर बनाने में कोई मदद/बेहतर समझने योग्य की सराहना की जाएगी।

Answer 1

एक रैखिक समाधान है, हालांकि यह गतिशील प्रोग्रामिंग का उपयोग नहीं करता है, बल्कि एक साधारण पाश और एक ढेर का उपयोग करता है। सबसे पहले आप निम्नलिखित अवलोकन कर सकते हैं: कंप्यूटिंग "c[i] से छोटे या बराबर लगातार तत्वों की संख्या" लगभग उतनी ही काम है जितनी अधिक "" जैसी अधिक सूचकांक "।

विचार इस प्रकार है: प्रत्येक i (बाएं i = 0 से व्यापक i = n - 1 दाईं ओर) के लिए, हम सभी सूचकांकों j ऐसा है कि सभी j < k < i के लिए c[j] > c[k] के सेट बनाए रखें। यह सेट एक ढेर में रखा जा सकता है, शीर्ष पर सबसे कम मूल्य। जब आप c[i] पढ़ते हैं, तब तक आप तत्वों को पॉप करते हैं जब तक कि आपको j जैसे c[j] > c[i] प्राप्त न हो। यह वांछित सूचकांक है। फिर आप स्टैक पर i दबा सकते हैं।

उदाहरण: s ढेर है। यहां ans[i]max{j <= i | c[j] > c[i]} होगा। ans[i] -1 होगा यदि पिछला सेट खाली है।

i 0 1 2 3 4 5 6 7 8 
c[i] 4 3 6 1 1 2 8 5 9 
------------------------ 
i = 0: 
    - s = []:  ans[0] = -1 
    - push i:  s = [0] 
i = 1: 
    - s = [0]: c[1] < c[0] -> ans[1] = 1 
    - push i:  s = [0, 1] 
i = 2: 
    - s = [0, 1]: c[2] >= c[1] -> pop 
     s = [0]: c[2] >= c[0] -> pop 
     s = []:  ans[2] = -1 
    - push i:  s = [2] 
i = 3: 
    - s = [2]: c[3] < c[2] -> ans[3] = 2 
    - push i:  s = [2, 3] 
i = 4: 
    - s = [2, 3]: c[4] >= c[3] -> pop 
     s = [2]: c[4] < c[2] -> ans[4] = 2 
    - push i:  s = [2, 4] 
i = 5 
    - s = [2, 4]: c[5] >= c[3] -> pop 
     s = [2]: c[5] < c[2] -> ans[5] = 2 
    - push i:  s = [2, 5] 
i = 6 
    - s = [2, 5]: c[6] >= c[5] -> pop  
     s = [2]: c[6] >= c[2] -> pop 
     s = [] -> ans[6] = -1 
    - push i:  s = [6] 
i = 7 
    - s = [6]: c[7] < c[6] -> ans[7] = 6 
    - push i:  s = [6, 7] 
i = 8 
    - s = [6, 7]: c[8] >= c[7] -> pop 
     s = [6]: c[8] >= c[6] -> pop 
     s = [] -> ans[8] = -1 
    - push i:  s = [8]  

Answer 2

(संपादक/मॉडरेटर कृपया इसे हटाने से पहले प्रश्न के चयनित उत्तर पर मेरी आखिरी टिप्पणी पढ़ें।)

ढेर संचालन

कुल विश्लेषण की हमारी पहली उदाहरण में, हम ढेर कर दिया गया है कि aug- एक नया संचालन के साथ mented का विश्लेषण। अनुभाग 10.1 दो मौलिक ढेर संचालन, हे (1) में समय लगता है, जिनमें से प्रत्येक प्रस्तुत:

PUSH (एस, एक्स) पर ढेर एस

पॉप (एस) वस्तु एक्स धक्का ढेर एस के शीर्ष पॉप और popped वस्तु लौटाता है।

चूंकि इनमें से प्रत्येक ऑपरेशन ओ (1) समय में चलता है, आइए हम प्रत्येक की लागत 1 पर विचार करें। एन पुश और पीओपी परिचालन के अनुक्रम की कुल लागत इसलिए एन है, और वास्तविक चलने का समय एन ऑपरेशन इसलिए है (एन)।

अब हम स्टैक ऑपरेशन मल्टीपॉप (एस, के) जोड़ते हैं, जो स्टैक एस के के शीर्ष ऑब्जेक्ट को हटा देता है, या पूरे स्टैक को पॉप करता है यदि इसमें के ऑब्जेक्ट्स से कम होता है। निम्नलिखित छद्म कोड में, ऑपरेशन STACK-EMPTY वर्तमान में स्टैक पर कोई ऑब्जेक्ट नहीं है, और अन्यथा गलत होने पर TRUE लौटाता है।

एस ऑब्जेक्ट्स के ढेर पर मल्टीपॉप (एस, के) का चलने का समय क्या है? वास्तविक चलने का समय वास्तव में निष्पादित पीओपी संचालन की संख्या में रैखिक होता है, और इस प्रकार पुश और पीओपी के लिए 1 प्रत्येक की अमूर्त लागत के संदर्भ में मल्टीपॉप का विश्लेषण करने के लिए पर्याप्त होता है। जबकि लूप के पुनरावृत्तियों की संख्या स्टैक से पॉप की गई वस्तुओं की संख्या न्यूनतम (एस, के) है। लूप के प्रत्येक पुनरावृत्ति के लिए, लाइन 2 में पीओपी को एक कॉल किया जाता है। इस प्रकार, मल्टीपॉप की कुल लागत न्यूनतम (एस, के) है, और वास्तविक चलने का समय इस लागत का एक रैखिक कार्य है।

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

कुल विश्लेषण का उपयोग करके, हम एक बेहतर ऊपरी सीमा प्राप्त कर सकते हैं जो एन संचालन के पूरे अनुक्रम को मानता है। वास्तव में, हालांकि एक एकल मल्टीपॉप ऑपरेशन महंगा हो सकता है, शुरुआती खाली स्टैक पर एन पुश, पीओपी, और मल्टीपॉप ऑपरेशंस का कोई अनुक्रम अधिकांश ओ (एन) पर खर्च कर सकता है। क्यूं कर? प्रत्येक ऑब्जेक्ट को हर बार धक्का दिया जा सकता है जब इसे धक्का दिया जाता है। इसलिए, कई बार पीओपी को गैर-स्टिकी स्टैक पर कॉल किया जा सकता है, जिसमें मल्टीपॉप के भीतर कॉल शामिल हैं, ज्यादातर पुश ऑपरेशंस की संख्या है, जो कि ज्यादातर एन है। एन के किसी भी मूल्य के लिए, एन पुश, पीओपी, और मल्टीपॉप ऑपरेशंस के किसी अनुक्रम में कुल ओ (एन) समय लगता है। ऑपरेशन की औसत लागत ओ (एन)/एन = ओ (1) है। कुल विश्लेषण में, हम प्रत्येक ऑपरेशन की अमूर्त लागत को औसत लागत के रूप में आवंटित करते हैं। इस उदाहरण में, इसलिए, सभी तीन स्टैक परिचालनों में ओ (1) की एक अमूर्त लागत है।