কম্পিউটার বিজ্ঞান হল অ্যালগরিদম এবং ডেটা স্ট্রাকচারের জটিলতা বোঝার বিষয়ে।
আপনার কাছে এমন আইটেমগুলির একটি তালিকা রয়েছে যা সাজানো দরকার, কিন্তু আরও জটিল বাছাই অ্যালগরিদম ব্যবহার করার জন্য আপনার কাছে সময় বা সংস্থান নেই৷
সন্নিবেশ বাছাই সহজতম বাছাই অ্যালগরিদমগুলির মধ্যে একটি, তবে এটি বড় তালিকার জন্য ধীর হতে পারে।
সহজ বাস্তবায়ন এবং বোঝাপড়া এই পদ্ধতিটিকে প্রোগ্রামারদের মধ্যে একটি প্রিয় করে তুলেছে। এটি ছোট তালিকার জন্য উপযুক্ত বা যখন আপনার দ্রুত সমাধানের প্রয়োজন হয়।
এই ব্লগ পোস্টে, আমরা সন্নিবেশ বাছাইয়ের সময় জটিলতা দেখব। এই অ্যালগরিদমটি অ্যারে সাজানোর জন্য ব্যবহৃত হয় এবং এটির রানটাইম O(n2) এর মানে হল যে সময়ের জটিলতা অ্যারের আকারের সাথে বৃদ্ধি পায়।
যাইহোক, এই অ্যালগরিদমটি প্রায়শই অন্যান্য সাজানোর অ্যালগরিদমের তুলনায় দ্রুত হতে পারে, যেমন কুইকসর্ট।
আসুন সন্নিবেশ বাছাই কিভাবে কাজ করে তা ঘনিষ্ঠভাবে দেখে নেওয়া যাক!
সন্নিবেশ সাজানোর অ্যালগরিদম কি?
এক সময়ে একটি উপাদান, সন্নিবেশ বাছাই একটি সাজানযোগ্য অ্যারে তৈরি করে, যাকে প্রায়শই একটি তালিকা বলা হয়।
উদাহরণস্বরূপ, কম্পাইলারগুলির মতো জটিল কম্পিউটার প্রোগ্রামগুলিতে বাছাই করা হয়, যেখানে টোকেনের ক্রম প্রোগ্রামের ব্যাখ্যার জন্য গুরুত্বপূর্ণ।
সন্নিবেশ বাছাই কিভাবে কাজ করে?
যখন আমরা একটি অ্যারে সাজানোর জন্য সন্নিবেশ সর্ট ব্যবহার করি, তখন অ্যালগরিদম তালিকার সবচেয়ে ছোট আইটেমটি খুঁজে বের করে সঠিক অবস্থানে সন্নিবেশ করে শুরু হয়।
তারপরে এটি পরবর্তী ক্ষুদ্রতম আইটেমটি খুঁজে বের করে এবং এটিকে সঠিক অবস্থানে সন্নিবেশিত করে এবং আরও অনেক কিছু।
অ্যালগরিদম তালিকার মধ্য দিয়ে লুপ করে কাজ করে, প্রতিটি আইটেমের সাথে তুলনা করে যা আগে আসে।
আইটেমগুলি ভুল ক্রমে থাকলে, অ্যালগরিদম তাদের অদলবদল করে। এটি তারপর তালিকাটি সাজানো হয়েছে কিনা তা পরীক্ষা করে, এবং যদি এটি হয়, অ্যালগরিদম শেষ হয়।
অনুশীলনে, সন্নিবেশ বাছাই প্রায়ই কোডের কয়েকটি লাইন ব্যবহার করে প্রয়োগ করা হয়, এটি ছোট অ্যারে সাজানোর জন্য একটি জনপ্রিয় পছন্দ করে তোলে। যাইহোক, এই অ্যালগরিদম ব্যবহার করার সময় সময় জটিলতা বিবেচনা করা উচিত।
উদাহরণ:
এখানে সন্নিবেশ বাছাই কিভাবে কাজ করে তার একটি উদাহরণ। আমরা নিম্নলিখিত অ্যারে ব্যবহার করব:
1, 2, 3, 4, 5, 6
অ্যালগরিদমটি তালিকার সবচেয়ে ছোট আইটেমটি খুঁজে বের করার মাধ্যমে শুরু হয়, যা হল 1। তারপর এটিকে সঠিক অবস্থানে, প্রথম অবস্থানে সন্নিবেশিত করে। এটি তারপর পরবর্তী ক্ষুদ্রতম আইটেমটি খুঁজে পায়, যা হল 2। এটি এটিকে সঠিক অবস্থানে সন্নিবেশিত করে, যা দ্বিতীয় অবস্থান।
এটি তারপর পরবর্তী ক্ষুদ্রতম আইটেমটি খুঁজে পায়, যা হল 3। এটি এটিকে সঠিক অবস্থানে সন্নিবেশিত করে, যা তৃতীয় অবস্থান।
এটি তারপরে পরবর্তী ক্ষুদ্রতম আইটেমটি খুঁজে পায়, যা হল 4। এটি এটিকে সঠিক অবস্থানে সন্নিবেশিত করে, যা চতুর্থ অবস্থান, ইত্যাদি। তালিকা এখন সাজানো!
আমরা উদাহরণ থেকে দেখতে পারি যে তালিকাটি সাজানোর জন্য অ্যালগরিদম ছয়টি তুলনা এবং অদলবদল করে। এটা n লাগে কারণ এই হয়2 n আইটেমগুলির একটি তালিকা সাজানোর জন্য তুলনা এবং অদলবদল। এই ক্ষেত্রে, n=6.
কিভাবে সন্নিবেশ বাছাই সময় জটিলতা উন্নত?
যদিও সন্নিবেশের সাজানোর একটি রানটাইম O(n2), এটি একটি ভাল বাছাই অ্যালগরিদম ব্যবহার করে উন্নত করা যেতে পারে, যেমন কুইকসর্ট।
Quicksort এর একটি O(n log n) রানটাইম রয়েছে, যা O(n) এর চেয়ে অনেক দ্রুত2).
যাইহোক, কিছু ক্ষেত্রে, সন্নিবেশ বাছাই দ্রুততর হতে পারে।
উদাহরণস্বরূপ, যদি তালিকাটি ইতিমধ্যেই ক্রমানুসারে থাকে, তাহলে সন্নিবেশ বাছাই করা কুইকসর্টের চেয়ে কম সময় নেবে।
অনুশীলনে, সন্নিবেশ বাছাই প্রায়ই কোডের কয়েকটি লাইন ব্যবহার করে প্রয়োগ করা হয়, এটি ছোট অ্যারে সাজানোর জন্য একটি জনপ্রিয় পছন্দ করে তোলে।
যাইহোক, এই অ্যালগরিদম ব্যবহার করার সময় সময় জটিলতা বিবেচনা করা উচিত।
সময়ের জটিলতা
সবচেয়ে খারাপ কেস জটিলতা O(n2):
সময়ের জটিলতা অ্যারের আকারের সাথে বৃদ্ধি পায়। এটা n লাগে2 n আইটেমগুলির একটি তালিকা সাজানোর জন্য তুলনা এবং অদলবদল।
উদাহরণস্বরূপ, যদি আমাদের আকার 1000 এর একটি অ্যারে থাকে, অ্যালগরিদম অ্যারে সাজানোর জন্য 1,000,000 তুলনা এবং অদলবদল নেবে।
সেরা কেস জটিলতা O(n):
সময়ের জটিলতা ইনপুট অ্যারের আকারের সমান। আমি
n আইটেমগুলির একটি তালিকা সাজানোর জন্য t তুলনা এবং অদলবদল করে। উদাহরণস্বরূপ, আকার 5 এর একটি অ্যারে বিবেচনা করুন৷ অ্যালগরিদম অ্যারে সাজানোর জন্য পাঁচটি তুলনা এবং অদলবদল নেবে৷
গড় কেস জটিলতা O(n2):
সময়ের জটিলতা এই ক্ষেত্রে সবচেয়ে খারাপ এবং সেরা ক্ষেত্রে জটিলতার মধ্যে।
এটা n লাগে2 n আইটেমগুলির একটি তালিকা সাজানোর জন্য তুলনা এবং অদলবদল।
সুতরাং, সন্নিবেশ বাছাই একটি স্থিতিশীল বাছাই অ্যালগরিদম।
কেন সন্নিবেশ বাছাই স্থিতিশীল?
সন্নিবেশ বাছাই স্থিতিশীল কারণ এটি ইনপুট অ্যারের সমান উপাদানের ক্রম সংরক্ষণ করে।
এটি অনেক অ্যাপ্লিকেশনের জন্য গুরুত্বপূর্ণ, যেমন ডেটা পুনরুদ্ধার বা আর্থিক বিশ্লেষণ। উদাহরণস্বরূপ, যদি আমাদের দুটি সংখ্যার তালিকা থাকে এবং সেগুলি তুলনা করতে চাই, তাহলে আমাদের নিশ্চিত করতে হবে যে উপাদানগুলির ক্রম সংরক্ষিত আছে।
তালিকাগুলি সাজানো না থাকলে, আমরা সঠিকভাবে তাদের তুলনা করব না।
নির্দেশিকা সমন্ধে মতামত দিন