algorithm - आम आदमी की शर्तों में जटिलता?




amortized-analysis (4)

एक परिमाणीकृत विश्लेषण में, डेटा-संरचना के संचालन के अनुक्रम को चलाने के लिए आवश्यक समय पर सभी कार्यों का प्रदर्शन किया जाता है ... अनुमानित विश्लेषण उस मामले में औसत-भिन्नता के विश्लेषण से भिन्न होता है; एक परिशोधित विश्लेषण सबसे खराब स्थिति में प्रत्येक ऑपरेशन के औसत प्रदर्शन की गारंटी देता है।

(कॉमन ऐट अल से, "परिचय से एल्गोरिदम")

यह थोड़ा भ्रमित हो सकता है, क्योंकि यह दोनों कहते हैं कि समय औसतन है, और यह औसत-केस विश्लेषण नहीं है। तो मुझे इसे एक वित्तीय सादृश्य के साथ समझाने की कोशिश करें (वास्तव में, "amortized" एक शब्द सबसे अधिक बैंकिंग और लेखा से जुड़ा हुआ है।)

मान लीजिए कि आप लॉटरी का संचालन कर रहे हैं (लॉटरी टिकट नहीं खरीदना, जिसे हम एक पल में लेंगे, लेकिन लॉटरी का संचालन करेंगे।) आप 100,000 टिकट प्रिंट करेंगे, जिसे आप प्रत्येक मुद्रा मुद्रा इकाई के लिए बेच देंगे। उन टिकटों में से एक को खरीदार को 40,000 मुद्रा इकाइयों के लिए अधिकार होगा।

अब, मान लें कि आप सभी टिकट बेच सकते हैं, आप 60,000 मुद्रा इकाइयों की कमाई कर सकते हैं: बिक्री में 100,000 मुद्रा इकाइयों, 40,000 मुद्रा इकाई पुरस्कार से घटाएं। आपके लिए, प्रत्येक टिकट का मूल्य 0.60 मुद्रा इकाई है, जो सभी टिकटों पर परिशोधित होता है। यह एक विश्वसनीय मूल्य है; इस पर भरोसा किया जा सकता है। यदि आप खुद को टिकट बेचने के थक गए हैं, और कोई व्यक्ति इसके साथ आता है और प्रत्येक को 0.30 मुद्रा इकाइयों के लिए बेचने की पेशकश करता है, तो आप जानते हैं कि आप कहां खड़े हैं।

लॉटरी खरीदार के लिए, स्थिति अलग है। खरीदार के पास लॉटरी टिकट खरीदने पर 0.60 मुद्रा इकाइयों की उम्मीद की कमी है। लेकिन यह संभावना है: क्रेता बिना जीत के 30 सालों (100,000 से अधिक टिकट) के लिए हर दिन दस लॉटरी टिकट खरीद सकता है। या वे एक दिन अकेले एक टिकट खरीद सकते हैं और 39,999 मुद्रा इकाइयों को जीत सकते हैं।

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

यह अक्सर कहा जाता है कि परिशोधन विश्लेषण उस स्थिति पर लागू होता है जहां उच्च लागत के संचालन दुर्लभ है, और यह अक्सर मामला है। लेकिन हमेशा नहीं। उदाहरण के लिए, तथाकथित "बैंकर की कतार" पर विचार करें, जो कि पहले-इन-प्रथम-आउट (फीफो) की कतार है, जो दो ढेर से बना है। (यह एक क्लासिक कार्यात्मक डेटा-संरचना है; आप अपरिवर्तनीय सिंगल लिंक वाले नोड्स से सस्ते लाइफो स्टैक का निर्माण कर सकते हैं, लेकिन सस्ता एफआईएफओ इतना स्पष्ट नहीं हैं)। संचालन निम्नानुसार लागू किया जाता है:

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

अब, मैं दावा करता हूं कि put और get की परिशोधित लागत O(1) , यह सोचते हुए कि मैं एक खाली कतार के साथ शुरू और समाप्त होता है। विश्लेषण सरल है: मैं हमेशा दाहिने हाथ की ढेर पर put हूं, और बाएं हाथ के ढेर से get हूं। If खंड से अलग हो, If प्रत्येक put एक push , और प्रत्येक को एक pop , जिनमें से दोनों O(1) । मुझे पता नहीं है कि मैं कितनी बार निष्पादित करूँगा If खंड - यह पॅट्स के पैटर्न पर निर्भर करता है और एस get - लेकिन मुझे पता है कि प्रत्येक तत्व दायां हाथ के ढेर से बाएं हाथ वाले स्टैक तक एक बार चलता है । इसलिए एन की पूरी अनुक्रमित लागत और एन के पूरे अनुक्रम पर यह है: n push es, n pop s, और n move s, जहां एक move एक pop जिसके बाद एक push : दूसरे शब्दों में, 2n put और 2n push ईएस और 2n pop एस में परिणाम get तो एक एकल put (या get ) की परिशोधित लागत एक push और एक pop

ध्यान दें कि बैंकर की कतारों को संक्षेप में कहा जाता है क्योंकि परिशोधी जटिलता विश्लेषण (और वित्त के साथ "परिशोधित" शब्द का संघ) बैंकर की कतारों का उत्तर आम साक्षात्कार प्रश्न का होता है, हालांकि मुझे लगता है कि अब इसे बहुत अच्छी तरह से ज्ञात माना जाता है: एक कतार के साथ आओ, जो निम्न तीन परिचालनों को परिशोधित ओ (1) समय में कार्यान्वित करता है:

1) कतार के सबसे पुराने तत्व को प्राप्त करें और निकालें,

2) कतार पर एक नया तत्व रखो,

3) वर्तमान अधिकतम तत्व का मान खोजें

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


"परिष्कृत जटिलता" का सिद्धांत यह है कि जब आप ऐसा करते हैं तो कुछ बहुत जटिल हो सकती है, क्योंकि यह अक्सर नहीं किया जाता है, यह "जटिल नहीं" माना जाता है। उदाहरण के लिए, यदि आप द्विआधारी पेड़ को समय-समय पर संतुलन बनाए रखने की ज़रूरत करते हैं - तो प्रत्येक 2^n प्रविष्टि में एक बार कहें - क्योंकि पेड़ को संतुलित करना काफी जटिल है, यह केवल प्रत्येक एन सम्मिलन में एक बार होता है (जैसे एक बार सम्मिलन संख्या 256 पर, फिर 512, 1024 वें, आदि पर) अन्य सभी सम्मिलन में, जटिलता ओ (1) है - हां, प्रत्येक एन सम्मिलन में ओ (एन) लेता है, लेकिन यह केवल 1/n संभावना है - इसलिए हम ओ (एन) को 1 / n से गुणा और ओ (1 )। ऐसा कहा जाता है कि "ओ (1) की जटिलता जटिलता" - क्योंकि जब आप अधिक तत्व जोड़ते हैं, तब पेड़ के पुन: संतुलन के लिए खाया जाने वाला समय कम होता है।


यह उस शाखा को निष्पादित करने की संभावना के साथ एक एल्गोरिथ्म में विभिन्न शाखाओं की सबसे खराब केस जटिलता को गुणा करने के समान है, और परिणाम जोड़ना इसलिए यदि कुछ शाखा को लेने की संभावना नहीं है, तो यह जटिलता के लिए कम योगदान देता है।


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

चूंकि सरणी पहले ही सॉर्ट किया गया है, हमें दोबारा सॉर्ट करने की ज़रूरत नहीं है हम कभी भी सबसे खराब स्थिति को एक बार से ज्यादा नहीं मारेंगे।

यदि हम सबसे छोटी को खोजने की कोशिश करने के एन क्वैरीज़ करते हैं, तो यह अभी भी ओ (एन लॉगन) होगा क्योंकि यह ओ (1) पर हावी है। यदि हम हर ऑपरेशन का समय औसत करते हैं तो यह होगा:

(एन लॉगन) / एन या हे (लॉगन) तो, समय की जटिलता / संचालन की संख्या

यह जटिलता जटिल है

मुझे लगता है कि यह कैसे जाता है, यह सिर्फ सीख रहा है im ..





amortized-analysis