Introselect
কম্পিউটার বিজ্ঞানে, ইন্ট্রোসেলেক্ট ("অন্তর্দৃষ্টিমূলক নির্বাচন"-এর সংক্ষিপ্ত রূপ) হল একটি সিলেকশন অ্যালগরিদম যা দ্রুত নির্বাচন এবং মিডিয়ান মিডিয়ানের একটি সংকর যার দ্রুত গড় কর্মক্ষমতা এবং সর্বোত্তম খারাপ-কেস কর্মক্ষমতা রয়েছে। ইন্ট্রোসেলেক্ট ইন্ট্রোসর্ট বাছাই অ্যালগরিদমের সাথে সম্পর্কিতঃ এগুলি মৌলিক দ্রুত নির্বাচন এবং দ্রুত বাছাই অ্যালগরিদমের অনুরূপ পরিমার্জন, যার মধ্যে তারা উভয়ই দ্রুত অ্যালগরিদম দিয়ে শুরু করে, যার ভাল গড় কর্মক্ষমতা এবং কম ওভারহেড রয়েছে, তবে দ্রুত অ্যালগরিদম দ্রুত যথেষ্ট অগ্রগতি না করলে সর্বোত্তম খারাপ-কেস অ্যালগরিদম (উচ্চতর ওভারহেড সহ)-এ ফিরে আসে। সি + + স্ট্যান্ডার্ড লাইব্রেরির জন্য জেনেরিক অ্যালগরিদম সরবরাহের উদ্দেশ্যে ডেভিড মুসার উভয় অ্যালগরিদমই প্রবর্তন করেছিলেন, যার মধ্যে দ্রুত গড় কর্মক্ষমতা এবং সর্বোত্তম খারাপ-কেস কর্মক্ষমতা উভয়ই রয়েছে, এইভাবে কর্মক্ষমতার প্রয়োজনীয়তাগুলি কঠোর করার অনুমতি দেয়। যাইহোক, বেশিরভাগ সি + + স্ট্যান্ডার্ড লাইব্রেরি বাস্তবায়নে, একটি ভিন্ন "ইন্ট্রোসেলেক্ট" অ্যালগরিদম ব্যবহার করা হয়, যা দ্রুত নির্বাচন এবং হিপসেলেক্টকে একত্রিত করে এবং ও (এন লগ এন) এর সবচেয়ে খারাপ-কেস চলমান সময় রয়েছে। 2022 সালের হিসাবে সি + + খসড়া মানটিতে সবচেয়ে খারাপ-কেস পারফরম্যান্সের প্রয়োজনীয়তা নেই, তাই এই ধরনের পছন্দের অনুমতি দেয়। অ্যালগরিদমস ইন্ট্রোসর্ট দ্রুতগতির সাথে তুলনীয় ব্যবহারিক কর্মক্ষমতা অর্জন করে ও (এন লগ এন) সবচেয়ে খারাপ-কেস আচরণ সংরক্ষণ করে দ্রুতগতির এবং হিপসর্টের একটি সংকর তৈরি করে। ইন্ট্রোসর্ট কুইকসোর্ট দিয়ে শুরু হয়, তাই যদি কুইকসোর্ট কাজ করে তবে এটি কুইকসোর্টের মতো পারফরম্যান্স অর্জন করে এবং যদি কুইকসোর্ট যথেষ্ট দ্রুত অগ্রগতি না করে তবে হিপসোর্টে ফিরে আসে (যার সর্বোত্তম খারাপ-কেস পারফরম্যান্স রয়েছে)। একইভাবে, ইন্ট্রোসেলেক্ট দ্রুত নির্বাচনের সাথে মিডিয়ানের সাথে দ্রুত নির্বাচনের সংমিশ্রণ করে দ্রুত নির্বাচনের মতো পারফরম্যান্সের সাথে সবচেয়ে খারাপ-কেস রৈখিক নির্বাচন অর্জন করে। ইন্ট্রোসেলেক্ট আশাবাদীভাবে দ্রুত নির্বাচন দিয়ে শুরু করে এবং শুধুমাত্র একটি খারাপ-কেস লিনিয়ার-টাইম সিলেকশন অ্যালগরিদম (মিডিয়ান অ্যালগরিদমের ব্লাম-ফ্লয়েড-প্র্যাট-রিভেস্ট-টার্জন মিডিয়ান)-এ স্যুইচ করে কাজ করে যদি এটি পর্যাপ্ত অগ্রগতি না করে অনেকবার পুনরাবৃত্তি করে। পরিবর্তন কৌশল হল অ্যালগরিদমের প্রধান প্রযুক্তিগত বিষয়বস্তু। কেবলমাত্র পুনরাবৃত্তিকে ধ্রুবক গভীরতায় সীমাবদ্ধ রাখা যথেষ্ট নয়, কারণ এটি অ্যালগরিদমকে সমস্ত পর্যাপ্ত বড় তালিকাগুলিতে স্যুইচ করতে বাধ্য করবে। মুসার কয়েকটি সহজ পদ্ধতি নিয়ে আলোচনা করেছেনঃ এখন পর্যন্ত প্রক্রিয়াজাত উপবিভাগগুলির আকারের তালিকার উপর নজর রাখুন। যদি কোনও সময়ে তালিকার আকার অর্ধেক না করে কে পুনরাবৃত্তিমূলক কল করা হয়, তবে কিছু ছোট ধনাত্মক কে-এর জন্য, সবচেয়ে খারাপ-কেস রৈখিক অ্যালগরিদমে স্যুইচ করুন। এখন পর্যন্ত উৎপন্ন সমস্ত বিভাজনের আকার যোগ করুন। যদি এটি তালিকার আকারের গুণিত কিছু ছোট ধনাত্মক ধ্রুবক k অতিক্রম করে, তবে সবচেয়ে খারাপ-ক্ষেত্রে রৈখিক অ্যালগরিদমে স্যুইচ করুন। এই যোগফলটি একটি একক স্কেলার চলকের মধ্যে ট্র্যাক করা সহজ। উভয় পদ্ধতিই পুনরাবৃত্তির গভীরতা কে-লগ এন = ও (লগ এন) এবং মোট চলমান সময়কে ও (এন)-এ সীমাবদ্ধ করে। গবেষণাপত্রে পরামর্শ দেওয়া হয়েছিল যে ইন্ট্রোসেলেক্ট নিয়ে আরও গবেষণা আসন্ন, কিন্তু লেখক 2007 সালে এই ধরনের আরও গবেষণা প্রকাশ না করেই অবসর নিয়েছিলেন। আরও দেখুন ফ্লয়েড-রিভেস্ট অ্যালগরিদম রেফারেন্স সিলেকশন অ্যালগরিদম