औसत मामले और अमूर्त विश्लेषण के बीच अंतर

Question

मैं एल्गोरिदम के अमूर्त विश्लेषण पर एक लेख पढ़ रहा हूं। निम्नलिखित एक टेक्स्ट स्निपेट है।

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

एक औसत मामले बाध्य संभावना है कि एक मिल जाएगा "बदकिस्मत" और एक इनपुट है कि अधिक से अधिक की उम्मीद समय भले ही आदानों की संभावना वितरण के लिए मान्यताओं मान्य हैं की आवश्यकता का सामना रोकता नहीं है।

ऊपर पाठ स्निपेट के बारे में मेरे सवाल कर रहे हैं:

1. पहले पैराग्राफ में, कैसे औसत दर-मामला विश्लेषण "डाटा संरचनाओं और संचालन के बारे में संभाव्य मान्यताओं पर भरोसा करते हैं?" करता है मैं औसत दर-मामला विश्लेषण पता इनपुट की संभावना पर निर्भर करता है, लेकिन उपर्युक्त कथन का क्या अर्थ है?

2. दूसरे पैराग्राफ में लेखक का क्या अर्थ है कि औसत वितरण मान्य नहीं है भले ही इनपुट वितरण मान्य है?

धन्यवाद!

Answer 1

1. औसत दर-मामला समय जटिलता पाने के लिए आपको क्या "औसत मामले" है के बारे में मान्यताओं बनाने की जरूरत है। यदि इनपुट स्ट्रिंग हैं, तो "औसत स्ट्रिंग" क्या है? क्या केवल लंबाई है? यदि हां, तो तारों की औसत लंबाई क्या होगी? यदि नहीं, तो इन तारों में औसत चरित्र क्या है? स्ट्रिंग्स उदाहरण के लिए अंतिम नाम हैं, तो इन सवालों का निश्चित रूप से जवाब देना मुश्किल हो जाता है। औसत अंतिम नाम क्या है?

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

Answer 2

1. एक अनुरक्षित सरणी में न्यूनतम की गणना पर विचार करें। शायद आप जानते हैं कि इसमें O(n) चलने का समय है, लेकिन यदि हम अधिक सटीक होना चाहते हैं तो यह औसत मामले में n/2 तुलना करता है। यही कारण है? क्योंकि हम डेटा पर एक धारणा कर रहे हैं; हम मानते हैं कि न्यूनतम संभावना एक ही संभावना के साथ हर स्थिति में हो सकती है। यदि हम इस धारणा को बदलते हैं, और हम उदाहरण के लिए कहते हैं कि i स्थिति में होने की संभावना उदाहरण के लिए बढ़ रही है, तो हम एक अलग तुलना संख्या साबित कर सकते हैं, यहां तक ​​कि एक अलग विषम सीमा भी।

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

Answer 3

औसत केस विश्लेषण इनपुट के बारे में धारणा बनाता है जो कुछ मामलों में पूरा नहीं हो सकता है। इसलिए, यदि आपका इनपुट यादृच्छिक नहीं है, तो सबसे खराब स्थिति में एल्गोरिदम का वास्तविक प्रदर्शन औसत मामले की तुलना में बहुत धीमा हो सकता है।

अमूर्त विश्लेषण ऐसी कोई धारणा नहीं करता है, लेकिन यह केवल एक ऑपरेशन के बजाय संचालन के अनुक्रम के कुल प्रदर्शन को मानता है।

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