कोई व्यक्ति आम आदमी की शर्तों में अमूर्त जटिलता को समझा सकता है? मुझे ऑनलाइन सटीक परिभाषा खोजने में कठिनाई हो रही है और मुझे नहीं पता कि यह पूरी तरह से एल्गोरिदम के विश्लेषण से कैसे संबंधित है। कुछ भी उपयोगी, भले ही बाहरी संदर्भित किया गया हो, अत्यधिक सराहना की जाएगी।आम आदमी की शर्तों में अमूर्त जटिलता?
"अमूर्त जटिलता" का सिद्धांत यह है कि यद्यपि ऐसा करने पर कुछ जटिल हो सकता है, क्योंकि यह अक्सर नहीं किया जाता है, इसे "जटिल नहीं" माना जाता है। उदाहरण के लिए, यदि आप एक बाइनरी पेड़ बनाते हैं जिसे समय-समय पर संतुलन की आवश्यकता होती है - एक बार प्रत्येक 2^n सम्मिलन कहें - क्योंकि पेड़ को संतुलित करना काफी जटिल है, यह केवल प्रत्येक एन सम्मिलन में होता है (उदाहरण के लिए एक बार सम्मिलन संख्या 256 पर, फिर फिर से 512 वें, 1024 वें, आदि)। अन्य सभी सम्मिलनों पर, जटिलता ओ (1) है - हाँ, यह प्रत्येक एन सम्मिलन के बाद ओ (एन) लेता है, लेकिन यह केवल 1/n संभावना है - इसलिए हम ओ (एन) को 1/n से गुणा करते हैं और ओ (1) प्राप्त करते हैं। इसलिए कहा जाता है कि "ओ (1) की अमूर्त जटिलता" - क्योंकि जैसे ही आप अधिक तत्व जोड़ते हैं, पेड़ को पुनर्व्यवस्थित करने के लिए खपत का समय न्यूनतम होता है।
"बड़े पर्याप्त" को इसके साथ क्या करना है? यहां अतिरिक्त विवरण हैं और संभावना से गुणा करने की मुख्य अवधारणा छोड़ दी गई है। – Potatoswatter
अयोग्य संशोधित प्रदर्शन गारंटी के पास संभावना के साथ कुछ भी नहीं है - वे संचालन के किसी अनुक्रम के लिए पूर्ण गारंटी हैं। संभाव्य प्रदर्शन के बारे में बात करते समय, "अपेक्षित" या "औसत-मामले" प्रदर्शन का संकेत देने वाली कला का एक शब्द उपयोग किया जाना चाहिए। – comingstorm
मैंने इसे "पर्याप्त पर्याप्त" को हटाने के लिए थोड़ा सा रेफ्रैज़ किया है (जिसके द्वारा मेरा मतलब था कि एक छोटे पेड़ को अक्सर बार-बार पुन: संतुलित किया जा सकता है, लेकिन एक बड़े व्यक्ति को अक्सर पुन: संतुलित नहीं किया जा रहा है - लेकिन मैं मानता हूं कि यह ' इसे रखने का एक बहुत अच्छा तरीका नहीं है, क्योंकि यह बढ़ता जा रहा है क्योंकि प्रयास बढ़ता है) –
अमूर्त माध्यमों का मतलब दोहराए गए रनों से विभाजित है। सबसे बुरी स्थिति व्यवहार की गारंटी है कि अधिक आवृत्ति के साथ न हो। उदाहरण के लिए यदि सबसे धीमा मामला ओ (एन) है, लेकिन ऐसा होने का मौका सिर्फ ओ (1/एन) है, और अन्यथा प्रक्रिया ओ (1) है, तो एल्गोरिदम अभी भी निरंतर ओ (1) समय को निरस्त कर देगा । बस प्रत्येक ओ (एन) के काम को एन अन्य रनों पर पार्सल करने के लिए विचार करें।
अवधारणा कुल समय को विभाजित करने के लिए पर्याप्त रन रखने पर निर्भर करती है। यदि एल्गोरिदम केवल एक बार चलाया जाता है, या इसे हर बार चलने पर एक समय सीमा पूरी करनी होती है, तो सबसे खराब स्थिति जटिलता अधिक प्रासंगिक होती है।
यह कुछ हद तक समान है जो उस शाखा को निष्पादित करने की संभावना के साथ एल्गोरिदम में विभिन्न शाखाओं की सबसे खराब केस जटिलता को गुणा करने और परिणामों को जोड़ने के समान है। इसलिए यदि कुछ शाखाओं को लेने की संभावना नहीं है, तो यह जटिलता को कम योगदान देता है।
परिशोधित जटिलता आपरेशन प्रति कुल व्यय, आपरेशन के एक दृश्य से अधिक का मूल्यांकन किया है।
विचार पूरे अनुक्रम की कुल व्यय की गारंटी देना है, जबकि अलग-अलग परिचालनों को अमूर्त लागत से अधिक महंगा होने की अनुमति है।
उदाहरण:
सी ++ std::vector<> के व्यवहार। जब push_back() अपने प्री-आवंटित मान से ऊपर वेक्टर आकार बढ़ाता है, तो यह आवंटित लंबाई को दोगुना करता है।
तो एक push_back() निष्पादित करने के लिए O(N) समय ले सकता है (क्योंकि सरणी की सामग्री को नई स्मृति आवंटन में कॉपी किया गया है)।
हालांकि, क्योंकि आवंटन का आकार दोगुना किया गया था, push_back() के बगल में N-1 कॉल प्रत्येक निष्पादित करने के लिए O(1) समय लगेगा। तो, कुल N संचालन अभी भी O(N) समय ले जाएगा; इस प्रकार push_back() प्रति ऑपरेशन O(1) की एक अमूर्त लागत दे रहा है।
जब तक अन्यथा उल्लिखित, परिशोधित जटिलता के संचालन के किसी भी क्रम के लिए एक asymptotic बुरी से बुरी हालत गारंटी नहीं है।इसका मतलब यह है:
बस गैर परिशोधित जटिलता के साथ के रूप में, बड़े-ओ परिशोधित जटिलता के लिए इस्तेमाल किया अंकन दोनों तय की प्रारंभिक भूमि के ऊपर और निरंतर प्रदर्शन कारकों पर ध्यान नहीं देता। इसलिए, बड़े-ओ अमूर्त प्रदर्शन का मूल्यांकन करने के उद्देश्य से, आप आम तौर पर मान सकते हैं कि एक निश्चित स्टार्टअप व्यय को कम करने के लिए अमूर्त परिचालनों का कोई अनुक्रम "काफी लंबा" होगा। विशेष रूप से, std::vector<> उदाहरण के लिए, इसीलिए आपको इस बारे में चिंता करने की आवश्यकता नहीं है कि आपको वास्तव में N अतिरिक्त संचालन का सामना करना पड़ेगा: विश्लेषण की एसिम्प्टोटिक प्रकृति पहले से ही मानती है कि आप करेंगे।
मनमाना लंबाई इसके अलावा, विश्लेषण परिशोधित संचालन, जिसकी लागत आप आकलन कर रहे हैं के अनुक्रम के बारे में मान्यताओं नहीं है - यह किसी भी संभव क्रम के संचालन की पर बुरी से बुरी हालत गारंटी नहीं है। इससे कोई फर्क नहीं पड़ता कि संचालन कितने बुरी तरह से चुने गए हैं (कहें, एक दुर्भावनापूर्ण विरोधी द्वारा!), एक अमूर्त विश्लेषण को यह गारंटी देनी चाहिए कि संचालन के लंबे समय तक अनुक्रम की लागत उनके अमूर्त लागतों की तुलना में लगातार अधिक नहीं हो सकती है। यही कारण है कि (जब तक विशेष रूप से क्वालीफायर के रूप में उल्लेख नहीं किया जाता है) "संभावना" और "औसत मामला" अमूर्त विश्लेषण के लिए प्रासंगिक नहीं हैं - वे सामान्य रूप से किसी भी सबसे बुरे मामले के बड़े-बड़े विश्लेषण के लिए हैं!
कभी-कभी एक उदाहरण एक की जरूरत है! :) – akki
एक परिशोधित विश्लेषण में, समय डेटा संरचना के संचालन के एक दृश्य करने के लिए आवश्यक सभी कार्यों से अधिक औसत है प्रदर्शन किया ... परिशोधित विश्लेषण है कि संभावना में से औसत दर-मामला विश्लेषण अलग है शामिल नहीं है ; एक अमूर्त विश्लेषण सबसे खराब मामले में प्रत्येक ऑपरेशन के औसत प्रदर्शन की गारंटी देता है।
(Cormen एट अल से। "एल्गोरिथम का परिचय")
कि थोड़ा भ्रमित हो सकता है, के बाद से यह कहते हैं दोनों उस समय औसत निकाला जाता है और यह कि इसके नहीं एक औसत दर-मामला विश्लेषण। तो मैं इसे वित्तीय सादृश्य के साथ समझाने की कोशिश करता हूं (वास्तव में, "अमूर्त" शब्द आमतौर पर बैंकिंग और लेखांकन से जुड़ा हुआ शब्द है।)
मान लीजिए कि आप लॉटरी का संचालन कर रहे हैं। (लॉटरी टिकट नहीं खरीदना, जिसे हम एक पल में प्राप्त करेंगे, लेकिन लॉटरी का संचालन स्वयं ही करेंगे।) आप 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 खंड से अलग, प्रत्येक putpush है, और प्रत्येक getpop है, जिनमें से दोनों O(1) हैं। मुझे नहीं पता कि मैं If खंड को कितनी बार निष्पादित करूंगा - यह put एस और get एस के पैटर्न पर निर्भर करता है - लेकिन मुझे पता है कि प्रत्येक तत्व दाएं हाथ के ढेर से बाएं हाथ के ढेर तक ठीक से चलता है । तो n n put रों का पूरा अनुक्रम और get रों पर कुल लागत है: n push तों, एन pop है, और एन move रों है, जहां एक move एक pop एक push द्वारा पीछा किया है: दूसरे शब्दों में, 2n put और get के परिणामस्वरूप 2 एन push ईएस और 2 एन pop एस। तो एक put (या get) की अमूर्त लागत एक push और एक pop है।
ध्यान दें कि बैंकर की कतारों को आम तौर पर अमूर्त जटिलता विश्लेषण (और वित्त के साथ "अमूर्त" शब्द के सहयोग के कारण कहा जाता है)। बैंकर की कतारें एक आम साक्षात्कार प्रश्न का उत्तर देती हैं, हालांकि मुझे लगता है कि अब यह बहुत प्रसिद्ध माना जाता है: एक कतार के साथ आओ जो अमूर्त ओ (1) समय में निम्नलिखित तीन ऑपरेशन लागू करता है:
1) जाओ और कतार की सबसे पुरानी तत्व निकाल,
2) कतार पर एक नए तत्व रखो,
3) वर्तमान अधिकतम तत्व का महत्व समझें।
+1 स्पष्ट रूप से यह बताते हुए कि संभावनाओं पर अमूर्त जटिलता पर कोई प्रभाव नहीं है, स्पष्ट उदाहरणों के लिए +1, संदर्भ कार्य उद्धृत करने के लिए +1 (कॉर्मन)। –
कहें कि आप एक अज्ञात सरणी के kth सबसे छोटे तत्व को खोजने का प्रयास कर रहे हैं। सरणी को सॉर्ट करना ओ (एन लॉगन) होगा। तो फिर केथ सबसे छोटी संख्या को ढूंढना सिर्फ इंडेक्स का पता लगा रहा है, इसलिए ओ (1)।
चूंकि सरणी पहले से ही क्रमबद्ध है, हमें फिर से क्रमबद्ध नहीं करना पड़ेगा। हम कभी भी सबसे खराब स्थिति परिदृश्य को एक से अधिक बार नहीं दबाएंगे।
यदि हम छोटे से छोटे स्थान का पता लगाने की कोशिश करने के एन प्रश्न पूछते हैं, तो यह अभी भी ओ (एन लॉगन) होगा क्योंकि यह ओ (1) पर हावी है। यदि हम प्रत्येक ऑपरेशन का समय औसत करते हैं तो यह होगा:
(एन लॉगन)/एन या ओ (लॉगन)। तो, समय जटिलता/संचालन की संख्या।
यह मिश्रित जटिलता है।
मैं इस बारे में सोच रहा है कि यह कैसे हो जाता है, im सिर्फ यह बहुत सीखने ..
http://en.wikipedia.org/wiki/Amortized_complexity –
http://stackoverflow.com/questions/11102585 http://स्टैक ओवरफ़्लो।कॉम/प्रश्न/1265 9931 http://stackoverflow.com/questions/14002391 http://programmers.stackexchange.com/questions/161404 –
संभावित डुप्लिकेट [एल्गोरिदम के अमूर्त विश्लेषण क्या है?] (https://stackoverflow.com/प्रश्न/11102585/एल्गोरिदम का क्या-अमूर्त-विश्लेषण-विश्लेषण) –