एनएसएससेट और एनएस डिक्शनरी

Question

के माध्यम से पुनरावृत्ति के लिए बड़े-ओ नोटेशन क्या हैं, मैं सोच रहा था कि एनएसएससेट के माध्यम से पुनरावृत्ति के लिए बड़े-बड़े नोटेशन क्या हैं। एनएसएआरएआरई का उत्तर स्पष्ट रूप से ओ (एन) है - लेकिन एनएसएससेट के लिए जवाब क्या है? इसके अलावा - मुझे लगता है कि वही उत्तर NSDictionary के लिए लागू होगा?

Answer 1

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

दिलचस्प बात यह है CFArray के समय जटिलता नहीं वास्तव में हे होने के लिए (एन) की गारंटी है:

कम्प्यूटेशनल जटिलता

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

ये समय जटिलताओं का सुझाव है कि CFArray (और इसलिए NSArray) वास्तव में एक पेड़ के रूप में लागू किया जा सकता है (परीक्षणों से पता चलता है कि यह यहां तक ​​कि कई अंतर्निहित डेटा संरचनाओं के बीच स्विच किया जा सकता है)।

CFDictionary के लिए इसी तरह

, सीमा दी काफी एक व्यापक रेंज है:

कम्प्यूटेशनल जटिलता

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

मैं CFSet के लिए कोर फाउंडेशन हेडर में एक समान टिप्पणी ढूँढने में सक्षम नहीं था, लेकिन स्रोत कोड के निरीक्षण से पता चलता है कि यह CFBasicHash है, जो एक हैश तालिका है पर आधारित है, इसलिए समय जटिलता के रूप में विशिष्ट होगा एक हैश टेबल के लिए - ओ (1) सम्मिलन, हटाने और परीक्षण आम तौर पर, और ओ (एन) सबसे खराब मामले में।

यदि आप वास्तव में यह पता लगाने में रुचि रखते हैं कि ये डेटा संरचनाएं कैसे काम करती हैं, कोर फाउंडेशन ओपन सोर्स है, तो आप Apple's website पर स्रोत कोड पढ़ सकते हैं।