javascript - तार 0(n) की तुलना क्यों कर रहा है, लेकिन संख्या 0(1) की तुलना कर रहा है?




computer-science equality (3)

मैं समझता हूं कि समानता के लिए दो तारों की तुलना करने के लिए, दुभाषिया को दोनों तारों के माध्यम से पुनरावृत्त करना पड़ता है और प्रत्येक चरित्र की तुलना करना पड़ता है।

यह समय जटिलता 0(n) जहां n सबसे छोटी स्ट्रिंग की लंबाई है।

हालांकि, समानता के लिए दो संख्याओं की तुलना 0(1)

ऐसा क्यों है? क्या समानता के लिए जाँच करने के लिए दुभाषिया को हर संख्या के माध्यम से पुनरावृत्त नहीं करना पड़ेगा?


तार

स्ट्रिंग की तुलना आम तौर पर वर्णों का एक रैखिक स्कैन होता है, पहले सूचकांक पर गलत लौटता है जहां वर्ण मेल नहीं खाते हैं।

समय की जटिलता O (N) है और लिया गया वास्तविक समय इस बात पर निर्भर करता है कि सांख्यिकीय रूप से भिन्न होने से पहले कितने पात्रों को स्कैन करने की आवश्यकता है। कोई सरल उत्तर नहीं है, लेकिन उत्तर फिर भी स्पष्ट है ;-)

नंबर

यदि दो पूर्णांक समान हैं, तो उनके सभी बिट्स की तुलना किए बिना जानना असंभव है। तो समानता के मामले में, आवश्यक समय बिट्स की संख्या के लिए आनुपातिक है (जो लॉग (एब्स (एन)) के लिए आनुपातिक है यदि एन तुलना में से एक है)।

यदि वे वास्तव में समान नहीं हैं, तो कई मामले हैं, जो कार्यान्वयन इंटर्नल्स के लिए प्रासंगिक हैं। लंबे ints को पॉवर-ऑफ -2 बेस में "अंक" के वेक्टर के रूप में संग्रहीत किया जाता है। यदि वैक्टर की लंबाई समान नहीं होती है, तो चींटियाँ बराबर नहीं होती हैं, और इसमें लगातार समय लगता है।

लेकिन अगर वे समान लंबाई वाले हैं, तो "अंक" की तुलना पहली (यदि कोई है) बेमेल जोड़ी को खोजने तक की जा सकती है। तुलना करने के लिए अंकों की संख्या के अनुपात में समय लगता है।


कंप्यूटर में संख्याओं को आमतौर पर निश्चित आकार की इकाइयों में संभाला जाता है। किसी भी भाषा और / या संकलक / प्लेटफ़ॉर्म संयोजन में एक int 32 या 64 बिट हो सकता है, लेकिन यह चर-लंबाई कभी नहीं होगा।

इसलिए आपके पास संख्याओं की तुलना करते समय बिट्स की एक निश्चित संख्या होती है। एक हार्डवेयर सर्किट बनाना बहुत आसान है जो एक साथ कई बिट्स की तुलना करता है (यानी "एक कार्रवाई" के रूप में)।

दूसरी ओर, स्ट्रिंग्स में स्वाभाविक रूप से परिवर्तनशील लंबाई होती है, इसलिए आप केवल "स्ट्रिंग" कह रहे हैं, आपको यह नहीं बताता है कि आपको कितने बिट्स की तुलना करनी होगी।

हालांकि, अपवाद हैं , क्योंकि चर-लंबाई संख्याएं हैं, जिन्हें आमतौर पर BigInteger या BigDecimal जैसे कुछ कहा जाता है जो String तुलना के समान व्यवहार करेगा क्योंकि यह दो BigDecimal मूल्यों की समानता (जहां n है) की तुलना करने के लिए O (n) हो सकता है BigDecimal s की लंबाई, उनके संख्यात्मक मानों की नहीं)।


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

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






equality