चलें कहते हैं कि मैं के रूप में एक सरणी है:सरणी में किसी तत्व को एक्सेस करने का निरंतर समय क्यों होता है?
पूर्णांक एक [] = {} 4,5,7,10,2,3,6
जब मैं इस तरह के एक के रूप में एक तत्व, का उपयोग [3] , वास्तव में दृश्य के पीछे क्या होता है? कई एल्गोरिदम पुस्तकें (जैसे कॉर्मन बुक ...) कहती हैं कि इसमें निरंतर समय लगता है?
(मैं निम्न स्तर के कार्यक्रमों की में सिर्फ एक noob हूँ तो मैं तुम लोगों से और अधिक जानने के लिए करना चाहते हैं)
बस पूरा होने के लिए, "रैखिक समय में किस संरचना का उपयोग किया जाता है?" Linked List संरचना रैखिक समय में उपयोग की जाती है। n तत्व प्राप्त करने के लिए आपको n-1 पिछले तत्वों से यात्रा करना है। आप जानते हैं, एक टेप रिकॉर्डर या वीएचएस कैसेट, जहां टेप/वीएचएस के अंत में जाना है, आपको लंबे समय तक इंतजार करना पड़ा :-)
एक सरणी हार्ड डिस्क के समान है: हर बिंदु है "निरंतर" समय में सुलभ :-)
यही कारण है कि कंप्यूटर की रैम को रैम कहा जाता है: रैंडम एक्सेस मेमोरी। यदि आप उस स्थान से पहले सभी मेमोरी को घुमाने के बिना अपना पता जानते हैं तो आप किसी भी स्थान पर जा सकते हैं।
कुछ लोगों ने मुझे बताया कि एचडी एक्सेस वास्तव में निरंतर समय में नहीं है (जहां पहुंच से मेरा मतलब है "सिर की स्थिति और एचडी के एक क्षेत्र को पढ़ने के लिए समय")। मुझे कहना है कि मुझे यकीन नहीं है। मैंने चारों ओर गुगल किया है और मुझे किसी को भी इसके बारे में बात नहीं मिली है। मुझे पता है कि समय रैखिक नहीं है, क्योंकि यह अभी भी यादृच्छिक रूप से उपयोग किया जाता है। अंत में, यदि आपको लगता है कि एचडी एक्सेस आपके लिए पर्याप्त स्थिर नहीं है (लेकिन फिर, लगातार क्या है? रैम का उपयोग? कैश, प्रीफेचिंग, डेटा लोकैलिटी और कंपाइलर ऑप्टिमाइज़ेशन पर विचार करना?), वाक्य पर विचार करने के लिए स्वतंत्र महसूस करें एक सरणी यूएसबी डिस्क स्टिक के समान ही है: प्रत्येक बिंदु "स्थिर" समय में पहुंच योग्य है :-)
हार्ड डिस्क एक यादृच्छिक अभिगम स्मृति के लिए एक बुरा उदाहरण हैं, क्योंकि यह वही है जो वे नहीं हैं। शायद यूएसबी स्टिक या ठोस-स्टेट डिस्क का उपयोग उदाहरण के रूप में करें? – blubb
हां और नहीं ... तकनीकी रूप से एचडी का "बाहरी" हिस्सा आंतरिक भाग से तेज़ है, लेकिन हम इसे अनदेखा करेंगे। एचडी पर एक फाइल तक पहुंच निरंतर समय में किया जाता है (या कम से कम रैखिक समय में नहीं)। यदि आपके पास एचडी पर एक फ़ाइल या एचडी पर एक मिलियन फाइलें हैं, तो उनमें से एक तक पहुंचने में एक ही समय लगेगा (बिल्कुल नहीं, लेकिन यह भौतिक वास्तविकता की तुलना में एक सैद्धांतिक मॉडल है :-))। – xanatos
क्या -1 समझाया जा सकता है? मैंने इसे थोड़ा सा विचार किया। एचडी एक्सेस समय निरंतर समय में है। एक एचडी को देखते हुए आपके पास मध्यम समय लगता है। तो एक फाइल की शुरुआत की मांग उस समय ले जाएगा। – xanatos
सरणी, प्रभावी ढंग से, एक स्मृति स्थान (एक सूचक) से जाना जाता है। a[3] तक पहुंच निरंतर समय में मिल सकती है, क्योंकि यह केवल location_of_a + 3 * sizeof (int) है।
सी में, आप इसे सीधे देख सकते हैं। याद रखें, a[3]*(a+3) जैसा ही है - जो यह कर रहा है (पॉइंटर "3 आइटम" को संदर्भित करने के संदर्भ में थोड़ा और स्पष्ट है)।
पर ध्यान देने योग्य है और क्योंकि '* (ए + 3)' '* (3 + ए) 'जैसा ही है, हम' [3] 'को' 3 [ए] 'के रूप में भी लिख सकते हैं, एक तथ्य हमेशा उपयोगी आईओसीसीसी और पसंद है। :-) – ShreevatsaR
@ShreevatsaR: हाँ, लेकिन ... लिखना '3 [ए]' में बहुत सारे व्यावहारिक उपयोग नहीं हैं - लेकिन '* (ए + 3)' का प्रयोग वास्तविक दुनिया परिदृश्यों में अक्सर उपयोगी होता है .. –
आपकी स्पष्टीकरण तब भी होगी जब उपयोग की जाने वाली अनुक्रमणिका भी एक चर होगी। लेकिन यहां से यह एक निरंतर ('3') है, सभी गणना गणना से पहले संकलक द्वारा भी की जा सकती है और रन टाइम पर प्रोग्राम सीधे मेमोरी तक पहुंच सकता है। तो वास्तव में यह केवल स्थिर नहीं है, बल्कि वास्तव में छोटा है। –
क्योंकि सरणी क्रमशः स्मृति में संग्रहीत हैं। तो वास्तव में, जब आप सरणी एक्सेस करते हैं [3] आप कंप्यूटर को बता रहे हैं, "सरणी की शुरुआत का मेमोरी पता प्राप्त करें, फिर इसमें 3 जोड़ें, फिर उस स्थान तक पहुंचें।" चूंकि जोड़ने में निरंतर समय लगता है, इसलिए सरणी पहुंच भी होती है!
"निरंतर समय" वास्तव में इसका अर्थ है "वह समय जो 'समस्या आकार' पर निर्भर नहीं है" । 'समस्या' के लिए "कंटेनर से कुछ प्राप्त करें", 'समस्या आकार' कंटेनर का आकार है।
एक सरणी तत्व तक पहुंचने से मूल रूप से कंटेनर आकार के बावजूद एक ही समय (यह एक सरलीकरण) होता है, क्योंकि तत्व को पुनर्प्राप्त करने के लिए चरणों का एक निश्चित सेट उपयोग किया जाता है: स्मृति में इसका स्थान (यह भी एक सरलीकरण है) की गणना की जाती है, और उसके बाद स्मृति में उस स्थान पर मान पुनर्प्राप्त किया जाता है।
उदाहरण के लिए, एक लिंक की गई सूची ऐसा नहीं कर सकती है, क्योंकि प्रत्येक लिंक अगले के स्थान को इंगित करता है। तत्व ढूंढने के लिए आपको पिछले सभी के माध्यम से काम करना होगा; औसतन, आप आधे कंटेनर के माध्यम से काम करेंगे, इसलिए कंटेनर का आकार स्पष्ट रूप से मायने रखता है।
9 के माध्यम से 10 पूर्णांक चर की एक सरणी, सूचकांक 0 के साथ, स्मृति पतों 2000, 2004, 2008, 2036 ... पर 10 शब्दों के रूप में जमा किया जा सकता है ताकि सूचकांक के साथ तत्व मैं पता 2000 + 4 × है मैं । इस प्रक्रिया को एक गुणा और के बाद से इन दो आपरेशन लगातार time.so ले एक अतिरिक्त ले हम कह सकते हैं पहुँच निरंतर समय में हो प्रदर्शन कर सकते हैं
यह वही है जो मैं चाहता था। यह स्थिर है लेकिन इसके पीछे गणित क्या है ---- आपने बहुत अच्छी तरह से समझाया है। –
एक सरणी अनुक्रमिक है, जिसका अर्थ यह है कि, सरणी में अगले तत्व का पता वर्तमान के बगल में। इसलिए यदि आप किसी सरणी के 5 वें तत्व प्राप्त करना चाहते हैं, तो आप 5 के साथ सरणी के मूल पते को संक्षेप में 5 वें तत्व के पते की गणना करते हैं। यह प्रत्यक्ष पता अब उस पते पर तत्व प्राप्त करने के लिए सीधे उपयोग किया जाता है।
अब आप आगे एक ही सवाल पूछ सकते हैं यहाँ "कैसे कंप्यूटर जानता है/गणना पते सीधे तक पहुँचता है?" यह कंप्यूटर मेमोरी (रैम) की प्रकृति और सिद्धांत है। यदि आप लगातार रुचि रखते हैं कि रैम निरंतर समय में किसी भी पते तक कैसे पहुंचता है, तो आप इसे किसी भी कंप्यूटर संगठन टेक्स्ट में पा सकते हैं या आप इसे Google पर ही देख सकते हैं।
ऐरे इसी प्रकार के डेटा का संग्रह है। तो सभी तत्वों memory.Therefore की एक ही राशि ले जाएगा अगर आप सरणी और डेटा के प्रकार के आधार पता यह मानती है तो आप आसानी से तत्व सरणी प्राप्त कर सकते हैं [i] निरंतर समय सूत्र का उपयोग कर में नीचे वर्णित:
int takes 4 bytes in a 32 bit system.
int array[10];
base address=4000;
location of 7th element:4000+7*4.
array[7]=array[4000+7*4];
इसलिए, यह स्पष्ट रूप से दिखाई देता है कि आप निरंतर समय में ith तत्व प्राप्त कर सकते हैं यदि आप मूल पता और उसके डेटा के प्रकार को जानते हैं। सरणी डेटा संरचना के बारे में अधिक जानने के लिए कृपया this पर जाएं।
यदि हमें स्मृति स्थान पता है जिसे एक्सेस किया जाना आवश्यक है तो यह पहुंच निरंतर समय में है। सरणी के मामले में स्मृति स्थान की गणना मूल सूचक, तत्व की अनुक्रमणिका और तत्व के आकार का उपयोग करके की जाती है। इसमें गुणा और अतिरिक्त ऑपरेशन शामिल है जो निष्पादित करने के लिए निरंतर समय लेता है। इसलिए सरणी के अंदर तत्व का उपयोग निरंतर समय लेता है।
यह क्यों कम हो गया है? कृपया स्पष्टीकरण प्रदान करें? – pixelearth
मुझे नहीं पता कि इसे क्यों वोट दिया गया है –
बस 10 अपवॉट्स। यह –