स्थिर समय (ओ (1)) में किए गए सरणी में किसी एकल तत्व का उपयोग क्यों कर रहा है?

Question

Wikipedia के अनुसार, किसी सरणी में किसी एक तत्व को एक्सेस करने में निरंतर समय लगता है क्योंकि इसे ढूंढने के लिए केवल एक ही ऑपरेशन किया जाना चाहिए।

मेरे लिए, पर्दे के पीछे क्या होता है शायद इस तरह दिखता है:

क) खोज रैखिक किया जाता है (मैं सूचकांक 0 पर खोज शुरू जैसे मैं तत्व 5. उपयोग करना चाहते है, अगर यह बराबर नहीं है 5 तक, मैं इंडेक्स 1 आदि पर जाता हूं) यह ओ (एन) है - जहां एन सरणी की लंबाई

बी) यदि सरणी बी-पेड़ के रूप में संग्रहीत की जाती है, तो यह ओ (लॉग एन)

मुझे कोई अन्य दृष्टिकोण नहीं दिख रहा है।

क्या कोई यह बता सकता है कि ओ (1) में यह क्यों और कैसे किया जाता है?

Answer 1

एक सरणी एक विशिष्ट स्मृति पते start पर शुरू होती है। एक तत्व बाइट element_size की एक निश्चित राशि पर कब्जा करता है। सरणी तत्व प्रारंभिक पते से स्मृति में एक के बाद एक स्थित हैं। तो आप start + i * element_size के साथ तत्व i के स्मृति पते की गणना कर सकते हैं। यह गणना सरणी आकार से स्वतंत्र है और O(1) के लिए है।

Answer 2

एक सरणी के सिद्धांत तत्वों में एक ही ज्ञात आकार के होते हैं और वे स्मृति के निरंतर भाग में स्थित होते हैं, इसलिए यदि सरणी की शुरुआत A मेमोरी पता पर स्थित है, तो यदि आप किसी तत्व को एक्सेस करना चाहते हैं तो आपको इसकी गणना करना है इस तरह का पता:

A + item_size*index इसलिए यह एक स्थिर समय ऑपरेशन है।

Answer 3

एक तत्व को एक्सेस करना उस तत्व को नहीं ढूंढ रहा है जिसका मूल्य x है।

तत्व को एक्सेस करना i का अर्थ है सरणी की स्थिति में तत्व प्राप्त करना।

यह O(1) में किया गया है क्योंकि यह बहुत सरल है (गणित की गणना की निरंतर संख्या) जहां तत्व इंडेक्स, सरणी की शुरुआत और प्रत्येक तत्व के आकार के आधार पर स्थित है।

रैम मेमोरी रैम में प्रत्येक पते तक पहुंचने के लिए निरंतर समय (या अधिक सटीक, बाध्य समय होने के लिए) प्रदान करता है, और पता लगाने के बाद ओ (1) है, और इसमें तत्व को पुनर्प्राप्त करना भी ओ है (1), यह आपको कुल O(1) देता है।

यह पता लगाना कि कोई तत्व जिसका मूल्य x है, वास्तव में Omega(n) समस्या है, जब तक कि सरणी पर कुछ और जानकारी न हो (उदाहरण के लिए, उदाहरण के लिए)।

Answer 4

आमतौर पर एक सरणी को स्मृति के निरंतर ब्लॉक के रूप में व्यवस्थित किया जाता है जहां प्रत्येक स्थिति को इंडेक्स गणना के माध्यम से एक्सेस किया जा सकता है। यह इंडेक्स गणना मनमाने ढंग से आकार के सरणी के लिए निरंतर समय में नहीं की जा सकती है, लेकिन एड्रेसेबल स्पेस के कारणों के लिए, शामिल संख्याएं मशीन शब्द आकार से बंधी हुई हैं, इसलिए निरंतर समय की धारणा उचित है।

Answer 5

यदि आपके पास Int की सरणी है। प्रत्येक int जावा में 32 बिट है। यदि आपके पास जावा में उदाहरण के 10 पूर्णांक हैं तो इसका मतलब है कि आप 320 बिट्स की स्मृति आवंटित करते हैं।फिर कंप्यूटर

0 पता है - सूचकांक उदाहरण के लिए स्मृति में है - 39200

पिछले सूचकांक स्मृति 39200 + अपने सरणी की कुल स्मृति में है = 39200 + 320 = 39520

तो फिर आपके द्वारा एक्सेस करना चाहते हैं सूचकांक 3. फिर यह 3 9 00 + 32 * 3 = 3 9 2 9 6 है।

यह सब निर्भर करता है कि आपके ऑब्जेक्ट में आप कितनी मेमोरी लेते हैं। बस याद रखें कि सरणी स्मृति के पूरे ब्लॉक को लेते हैं।