javascript - স্ট্রিং 0(এন) এর সাথে তুলনা করা হলেও 0(1) সংখ্যার তুলনা করা কেন?




computer-science equality (3)

আমি বুঝতে পারি যে সমতার জন্য দুটি স্ট্রিং তুলনা করতে, দোভাষীকে উভয় স্ট্রিং দিয়ে পুনরাবৃত্তি করতে হবে এবং প্রতিটি অক্ষরকে তুলনা করতে হবে।

এটি সময়ের জটিলতা 0(n) যেখানে n হ'ল সংক্ষিপ্ততম স্ট্রিংয়ের দৈর্ঘ্য।

তবে সমতার জন্য দুটি সংখ্যার তুলনা করা 0(1)

তা কেন? দোভাষীকে কি সমতা পরীক্ষা করতে প্রতিটি সংখ্যার মাধ্যমে পুনরাবৃত্তি করতে হবে না?


দড়ি

স্ট্রিং তুলনাগুলি হ'ল অক্ষরগুলির একটি লিনিয়ার স্ক্যান, প্রথম সূচীতে যেখানে অক্ষর মেলে না সেখানে মিথ্যা ফিরিয়ে দেয়।

সময় জটিলতা হ'ল (এন) এবং নেওয়া প্রকৃত সময় নির্ভর করে পরিসংখ্যানগতভাবে পার্থক্য প্রকাশের আগে কত অক্ষর স্ক্যান করা দরকার। একটি সহজ উত্তর নেই, তবে উত্তরটি তবুও সুস্পষ্ট ;-)

নাম্বার

যদি দুটি পূর্ণসংখ্যা সমান হয় তবে তাদের সমস্ত বিটের তুলনা না করে জানা অসম্ভব। সুতরাং সাম্যতার ক্ষেত্রে, প্রয়োজনীয় সময়টি বিটের সংখ্যার সাথে আনুপাতিক (যা ল এর তুলনায় সমানুপাতিক (অ্যাবস (এন)) হয় যদি এন এর তুলনাগুলির মধ্যে একটি হয়)।

যদি তারা বাস্তবে সমান না হয়, তবে অনেকগুলি মামলা রয়েছে, যা বাস্তবায়নের অভ্যন্তরের সাথে সম্পর্কিত all লম্বা ints একটি পাওয়ার-অফ -2 বেসে "অঙ্কগুলি" এর ভেক্টর হিসাবে সংরক্ষণ করা হয়। যদি ভেক্টরগুলির একই দৈর্ঘ্য না থাকে তবে ইনটগুলি সমান নয় এবং এটি ধ্রুবক সময় নেয়।

তবে যদি সেগুলি একই দৈর্ঘ্য হয়, তবে প্রথম (যদি কোনও) মিল না পাওয়া জোড় খুঁজে না পাওয়া পর্যন্ত "অঙ্কগুলি" তুলনা করতে হবে। এটি তুলনামূলকভাবে প্রয়োজন সংখ্যার সাথে সময় সমানুপাতিক লাগে।


কম্পিউটারে নম্বরগুলি সাধারণত স্থির আকারের ইউনিটে পরিচালিত হয়। কোনও প্রদত্ত ভাষা এবং / অথবা সংকলক / প্ল্যাটফর্মের সংমিশ্রণে কোনও int 32 বা 64 বিট হতে পারে, তবে এটি কখনই পরিবর্তনশীল-দৈর্ঘ্যের হতে পারে না।

সুতরাং সংখ্যার তুলনা করার সময় তুলনা করার জন্য আপনার কাছে বিটগুলির একটি নির্দিষ্ট সংখ্যা রয়েছে। এমন একটি হার্ডওয়ার সার্কিট তৈরি করা খুব সহজ যা বহু বিটকে একবারে তুলনা করে (যেমন "একটি ক্রিয়া" হিসাবে)।

অন্যদিকে স্ট্রিংগুলির সহজাত পরিবর্তনশীল দৈর্ঘ্য রয়েছে, সুতরাং আপনি কেবল "স্ট্রিং" বলছেন আপনাকে কত বিট তুলনা করতে হবে তা আপনাকে জানায় না।

তবে ব্যতিক্রমগুলি রয়েছে যেমন ভেরিয়েবল-দৈর্ঘ্যের সংখ্যা রয়েছে, সাধারণত BigInteger বা BigDecimal মতো কিছু বলা হয় যা String তুলনার সাথে খুব একই রকম আচরণ করবে কারণ এটি সমানতার জন্য দুটি BigDecimal মান (যেখানে এন হয় BigDecimal এর দৈর্ঘ্য, তাদের সংখ্যাসূচক মানগুলির মধ্যে নয়)।


সাধারণত প্রোগ্রামগুলি স্থির আকারের ডেটা স্ট্রাকচার হিসাবে সংখ্যাগুলি উপস্থাপন করে (বাইনারি মান, যার কারণে আপনি বিটগুলিতে বর্ণিত তাদের আকারগুলি দেখতে পারেন)। স্থির আকারের কারণে, তুলনাগুলি একটি ধ্রুবক সময় নেয় এবং ও (1) হয়, যা এই জাতীয় প্রতিনিধিত্বের অন্যতম সুবিধা। একটি খারাপ দিক প্রতিনিধিত্ব করা যেতে পারে যে মান সীমার একটি সীমা হতে হবে।

একটি বিকল্প প্রতিনিধিত্ব যা এই সীমাবদ্ধতাটি সরিয়ে দেয়, নির্বিচারে-বৃহত সংখ্যার সংখ্যার জন্য অনুমতি দেয়, সুতরাং আর আকারে স্থির হবে না এবং তুলনা করার জন্য আর (1) থাকবে না।





equality