algorithm - लगातार अमूर्त समय




complexity-theory big-o (4)

अमूर्त समय सरल शब्दों में समझाया गया है:

यदि आप एक ऑपरेशन करते हैं तो दस लाख बार कहते हैं, आपको वास्तव में सबसे बुरी स्थिति या उस ऑपरेशन का सबसे अच्छा मामला नहीं है - आप जिस चीज की परवाह करते हैं, यह है कि जब आप ऑपरेशन को दस लाख बार दोहराते हैं तो कुल मिलाकर कितना समय लगता है ।

इसलिए इससे कोई फर्क नहीं पड़ता कि ऑपरेशन थोड़ी देर में धीमा हो जाता है, जब तक "थोड़ी देर में" धीमा होने के लिए धीमा होने के लिए पर्याप्त दुर्लभ होता है। अनिवार्य रूप से अमूर्त समय का अर्थ है "यदि आप कई संचालन करते हैं तो प्रति ऑपरेशन औसत समय लिया जाता है"। अमूर्त समय स्थिर नहीं होना चाहिए; आप रैखिक और लॉगरिदमिक अमूर्त समय या जो कुछ भी हो सकते हैं।

आइए गतिशील सरणी के मैट्स का उदाहरण लें, जिसमें आप बार-बार नए आइटम जोड़ते हैं। आम तौर पर एक आइटम जोड़ना निरंतर समय लेता है (यानी, O(1) )। लेकिन हर बार सरणी भर जाती है, आप दो गुना अधिक स्थान आवंटित करते हैं, अपने डेटा को नए क्षेत्र में कॉपी करते हैं, और पुरानी जगह को मुक्त करते हैं। आवंटित मानते हैं और निरंतर समय में दौड़ते हैं, इस विस्तार प्रक्रिया में O(n) समय लगता है जहां एन सरणी का वर्तमान आकार है।

तो हर बार जब आप विस्तार करते हैं, तो आप अंतिम विस्तार के रूप में लगभग दोगुना समय लेते हैं। लेकिन आप इसे करने से पहले दो बार इंतजार कर चुके हैं! प्रत्येक विस्तार की लागत इस प्रकार सम्मिलन के बीच "फैल" जा सकती है। इसका मतलब है कि लंबी अवधि में, सरणी में एम आइटम जोड़ने के लिए लिया गया कुल समय O(m) , और इसलिए अमूर्त समय (यानी प्रति प्रविष्टि समय) O(1)

एल्गोरिदम की समय जटिलता के बारे में बात करते समय "निरंतर अमूर्त समय" का क्या अर्थ है?


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

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

या अधिक सख्त शर्तों में,

एक स्थिर सी है, जैसे लम्बाई एल के संचालन के प्रत्येक अनुक्रम (एक महंगा ऑपरेशन के साथ समाप्त होने वाला) के लिए, समय सी * एल (धन्यवाद राफल डॉउगर्ड ) से अधिक नहीं है


ऊपर दिए गए स्पष्टीकरण कुल विश्लेषण पर लागू होते हैं, कई परिचालनों पर "औसत" लेने का विचार। मुझे यकीन नहीं है कि वे बैंकर्स-विधि या अमूर्त विश्लेषण के भौतिकविदों के तरीकों पर कैसे लागू होते हैं।

अभी व। मुझे सही जवाब का बिल्कुल यकीन नहीं है। लेकिन इसे दोनों भौतिकविदों + बैंकर के तरीकों की सिद्धांत स्थिति के साथ करना होगा:

(परिचालन की लागत-लागत की राशि)> = (संचालन की वास्तविक लागत का योग)।

मुझे जिस मुख्य कठिनाई का सामना करना पड़ता है वह यह है कि ऑपरेशन की अमूर्त-एसिम्प्टोटिक लागत सामान्य-एसिम्प्टोटिक लागत से भिन्न होती है, मुझे यकीन नहीं है कि अमूर्त लागतों के महत्व को कैसे रेट किया जाए।

वह तब होता है जब कोई मेरी अमूर्त लागत प्रदान करता है, मुझे पता है कि यह सामान्य-एसिम्प्टोटिक लागत के समान नहीं है, तो मुझे अमूर्त लागत से क्या निष्कर्ष निकालना है?

चूंकि हमारे पास कुछ परिचालनों का अधिभार होने पर मामला अधिक चार्ज होने का मामला है, इसलिए एक परिकल्पना यह हो सकती है कि अलग-अलग परिचालनों की अमूर्त लागतों का अर्थ व्यर्थ होगा।

उदाहरण के लिए: एक फाइबोनैकी ढेर के लिए, ओ (1) होने के लिए केवल घटती-कुंजी की अमूर्त लागत को उद्धृत करना अर्थहीन है क्योंकि "ढेर की क्षमता में वृद्धि के पहले कार्यों द्वारा किए गए कार्यों" द्वारा लागत कम हो जाती है।

या

हम एक और परिकल्पना कर सकते हैं कि अमूर्त लागतों के कारण निम्नानुसार हैं:

  1. मुझे पता है कि महंगी ऑपरेशन मल्टीपल लो-कॉस्ट ऑपरेशंस से पहले जा रहा है।

  2. विश्लेषण के लिए, मैं कुछ कम लागत वाली परिचालनों को अधिभारित करने जा रहा हूं, इस तरह उनके एस्पाटोटिक-लागत में परिवर्तन नहीं होता है।

  3. इन बढ़ते कम लागत वाले परिचालनों के साथ, मैं यह साबित कर सकता हूं कि विस्तारित ऑपरेशन में एक लघु ASMPTOTIC लागत है।

  4. इस प्रकार मैंने एन संचालन की लागत के ASYMPTOTIC-BOUND में सुधार / कमी आई है।

इस प्रकार अमूर्त लागत विश्लेषण + अमूर्त-लागत-सीमाएं केवल महंगी परिचालनों पर लागू होती हैं। सस्ते परिचालनों में समान एसिम्प्टोटिक-अमूर्त लागत है जो उनके सामान्य-एसिम्प्टोटिक-लागत के रूप में होती है।


मैं 3 बार के लिए दोहराने के बाद विकिपीडिया स्पष्टीकरण के नीचे उपयोगी पाया:

स्रोत: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

"गतिशील ऐरे

एक गतिशील ऐरे के लिए पुश ऑपरेशन का अमूर्त विश्लेषण

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

आम तौर पर यदि हम आकार n की सरणी में एन को धक्का देने के मनमाना संख्या पर विचार करते हैं, तो हम देखते हैं कि पुश ऑपरेशंस को अंतिम समय को छोड़कर स्थिर समय लगता है जो आकार दोगुनी ऑपरेशन करने के लिए ओ (एन) समय लेता है। चूंकि वहां एन ऑपरेशंस कुल थे, हम इसका औसत ले सकते हैं और पाते हैं कि गतिशील सरणी पर तत्वों को धक्का देने के लिए: ओ (एन / एन) = ओ (1), स्थिर समय होता है। "

एक साधारण कहानी के रूप में मेरी समझ के लिए:

मान लें कि आपके पास बहुत पैसा है। और, आप उन्हें एक कमरे में ढेर करना चाहते हैं। और, आपके पास लंबे हाथ और पैरों हैं, जितनी देर तक आपको भविष्य में या भविष्य में चाहिए। और, आपको सभी को एक कमरे में भरना होगा, इसलिए इसे लॉक करना आसान है।

तो, आप कमरे के अंत / कोने पर जाते हैं और उन्हें ढेर करना शुरू करते हैं। जैसे ही आप उन्हें ढेर करते हैं, धीरे-धीरे कमरा अंतरिक्ष से बाहर हो जाएगा। हालांकि, जैसा कि आप भरते हैं उन्हें ढेर करना आसान था। पैसा मिला, पैसे डाल दिया। आसान। यह ओ (1) है। हमें किसी भी पिछले पैसे को स्थानांतरित करने की आवश्यकता नहीं है।

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

दूसरे शब्दों में, एन, केवल 1 ऑपरेशन तक आसान था, लेकिन जब हमें एक बड़े कमरे में जाने की जरूरत होती है, तो हमने एन ऑपरेशन किया। तो, दूसरे शब्दों में, यदि हम औसत करते हैं, तो शुरुआत में 1 डालने वाला होता है, और दूसरे कमरे में जाने के दौरान 1 और कदम होता है। कुल 2 ऑपरेशन, एक डालने, एक कदम।

मान लीजिए कि छोटे कमरे में भी 1 मिलियन की तरह बड़ा है, एन (1 मिलियन) की तुलना में 2 ऑपरेशन वास्तव में तुलनीय संख्या नहीं है, इसलिए इसे निरंतर या ओ (1) माना जाता है।

मान लीजिए कि जब हम उपरोक्त सभी बड़े कमरे में करते हैं, और फिर आगे बढ़ने की जरूरत है। यह अभी भी वही है। कहें, एन 2 (कहें, 1 अरब) बड़े कमरे में धन की गिनती की नई राशि है

तो, हमारे पास एन 2 है (जिसमें पिछली बार शामिल है क्योंकि हम सभी को छोटे से बड़े कमरे में ले जाते हैं)

हमें अभी भी केवल 2 ऑपरेशन की आवश्यकता है, एक बड़ा कमरा में डाला जाता है, फिर एक और कदम ऑपरेशन भी एक बड़े कमरे में जाने के लिए।

तो, यहां तक ​​कि एन 2 (1 अरब) के लिए, यह प्रत्येक के लिए 2 संचालन है। जो फिर से कुछ नहीं है। तो, यह स्थिर है, या ओ (1)

इसलिए, जैसे एन एन से एन 2 तक बढ़ता है, या अन्य, इससे कोई फर्क नहीं पड़ता। यह अभी भी निरंतर है, या ओ (1) संचालन प्रत्येक एन के लिए आवश्यक है।

अब मान लें, आपके पास 1 के रूप में एन है, बहुत छोटा है, पैसे की गिनती छोटी है, और आपके पास एक बहुत छोटा कमरा है, जो केवल 1 गिनती के बराबर होगा।

जैसे ही आप कमरे में पैसे भरते हैं, कमरा भर जाता है।

जब आप बड़े कमरे में जाते हैं, तो मान लें कि इसमें केवल एक और पैसा फिट हो सकता है, कुल 2 पैसे की गणना। इसका मतलब है, पिछले स्थानांतरित धन और 1 और। और फिर यह भर गया है।

इस तरह, एन धीरे-धीरे बढ़ रहा है, और यह अब निरंतर ओ (1) नहीं है, क्योंकि हम पिछले कमरे से सभी पैसे ले जा रहे हैं, लेकिन केवल केवल 1 और पैसे फिट कर सकते हैं।

100 बार के बाद, नया कमरा पिछले से 100 गुना धन और 1 और धन को समायोजित कर सकता है। यह ओ (एन) है, चूंकि ओ (एन + 1) ओ (एन) है, यानी, 100 या 101 की डिग्री समान है, दोनों सैकड़ों हैं, पिछली कहानी के विपरीत, लाखों लोगों और अरबों के लिए ।

इसलिए, यह हमारे पैसे (चर) के लिए कमरे आवंटित करने का अक्षम तरीका है (या स्मृति / रैम)।

तो, 2 की शक्तियों के साथ, एक अच्छा तरीका अधिक कमरे आवंटित कर रहा है।

पहला कमरा आकार = पैसे की 1 गिनती फिट बैठता है
दूसरा कमरा आकार = पैसे की 4 गिनती फिट बैठता है
तीसरा कमरा आकार = पैसे की 8 गिनती फिट बैठता है
चौथा कमरा आकार = पैसे की 16 गिनती फिट बैठता है
5 वां कमरा आकार = पैसे की 32 गिनती फिट बैठता है
6 वें कमरे का आकार = पैसे की 64 गिनती फिट बैठता है
7 वां कमरा आकार = पैसे की 128 गिनती फिट बैठता है
8 वें कमरे का आकार = पैसे की 256 गिनती फिट बैठता है
9वीं कमरा आकार = पैसे की 512 गिनती फिट बैठता है
10 वें कमरे का आकार = पैसे की 1024 गिनती फिट बैठता है
11 वें कमरे का आकार = पैसे की 2,048 गिनती फिट बैठता है
...
16 वें कमरे का आकार = 65,536 पैसे की गिनती फिट बैठता है
...
32 वें कमरे का आकार = 4,294,967,296 पैसे की गिनती फिट बैठता है
...
64 वें कमरे का आकार = 18,446,744,073,70 9,551,616 पैसे की गिनती फिट बैठता है

यह बेहतर क्यों है? क्योंकि यह शुरुआत में धीरे-धीरे बढ़ने लगता है, और बाद में तेज़ी से, यह हमारी रैम में स्मृति की मात्रा की तुलना में है।

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

हालांकि, अंतिम मामले में, 2 की शक्तियां, यह हमारी रैम की सीमाओं में बढ़ती है। और इसलिए, 2 की शक्तियों में वृद्धि, दोनों आर्मोटिज्ड विश्लेषण निरंतर बना रहता है और यह सीमित रैम के लिए अनुकूल है जो हमारे पास आज है।





big-o