মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
ডিভাইড এন্ড কনকার অ্যালগোরিদম
যে কয়টি সর্টিং অ্যালগোরিদম এই পর্যন্ত আমরা দেখেছি সেগুলোর মধ্যে, সিলেকশন সর্ট এবং ইনসারশন সর্ট, এর \Theta, left parenthesis, n, squared, right parenthesis সময়ের মধ্যে সবচেয়ে বাজে রান করার সময় রয়েছে। যখন ইনপুট অ্যারের আকার অনেক বড় হয়, এই অ্যালগোরিদমগুলো রান করতে অনেক বেশি সময় নিবে। এই অনুশীলনীতে এবং এর পরের অনুশীলনীতে, আমরা আরও দুইটি সর্টিং অ্যালগোরিদম দেখব, মার্জ সর্ট এবং কুইকসর্ট, যে অ্যালগোরিদমগুলোর রান করার সময়কাল একটু ভালো। সাধারণভাবে, বেশিরভাগ ক্ষেত্রে মার্জ সর্ট \Theta, left parenthesis, n, \lg, n, right parenthesis সময়ে রান করে থাকে এবং কুইকসর্ট বেশিরভাগ ক্ষেত্রে এবং গড়ে \Theta, left parenthesis, n, \lg, n, right parenthesis সময়ে রান করে থাকে, যদিও সবচেয়ে খারাপ-ক্ষেত্রে এর রান করার সময়কাল হল \Theta, left parenthesis, n, squared, right parenthesis। এখানে একটি ছক দেওয়া হল যেখানে এই চারটি সর্টিং অ্যালগোরিদম এবং তাদের রান করার সময়কাল দেওয়া হল:
| অ্যালগোরিদম | সবচেয়ে খারাপ ক্ষেত্রে এর রান করার সময়কাল | সবচেয়ে ভালো ক্ষেত্রে রান করার সময় | গড়-ক্ষেত্রে এর রান করার সময় |
|---|---|---|---|
| সিলেকশন সর্ট | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, squared, right parenthesis |
| ইনসারশন সর্ট | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, right parenthesis, স, ম, য় | \Theta, left parenthesis, n, squared, right parenthesis |
| মার্জ সর্ট | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |
| কুইকসর্ট | \Theta, left parenthesis, n, squared, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis | \Theta, left parenthesis, n, \lg, n, right parenthesis |
ডিভাইড-এন্ড-কনকার
মার্জ সর্ট এবং কুইকসর্ট এই দুইটি অ্যালগোরিদমই পুনরাবৃত্তির উপরে ভিত্তি করে সাধারণ একটি অ্যালগোরিদমিক উদাহরণ নিযুক্ত করে থাকে। এই ডিভাইড এন্ড কনকার উদাহরণটি, একটি সমস্যাকে ছোট ছোট সমস্যাতে বিভক্ত করে ফেলে যেগুলো মূল সমস্যার অনুরূপ, পুনরাবৃত্তির মাধ্যমে কাজ করে এই ছোট সমস্যাগুলো সমাধান করে থাকে এবং সবশেষে এই ছোট সমস্যাগুলোর সমাধান একসাথে করার মাধ্যমে মূল সমস্যাটি সমাধান করা হয়। কারণ ডিভাইড এন্ড কনকার এই ছোট সমস্যাগুলো পুনরাবৃত্তির মাধ্যমে সমাধান করে থাকে, প্রতিটি ছোট সমস্যা অবশ্যই মূল সমস্যাটি থেকে ছোট হতে হবে এবং ছোট সমস্যাগুলোর জন্য অবশ্যই একটি ভিত্তি থাকতে হবে। আমাদের এখানে মনে রাখা দরকার ডিভাইড এন্ড কনকার অ্যালগোরিদমের তিনটি অংশ রয়েছে:
- বিভক্তি: মূল সমস্যাটি কতগুলো ছোট ছোট সমস্যাতে বিভক্ত করে ফেলতে হবে যেটা হবে একই মূল সমস্যার ছোট রূপ।
- জয়: ছোট সমস্যাগুলো পুনরাবৃত্তি ব্যবহার করার মাধ্যমে সমাধান করা যায়। যদি তারা বেশ ছোট আকারের সমস্যা হয়, তাহলে এই ছোট সমস্যাগুলো বেস কেস হিসেবে সমাধান করা যায়।
- একত্রীকরণ: ছোট সমস্যার সমাধানগুলো সংযুক্ত করলে মূল সমস্যার সমাধান হয়ে যাবে।
তুমি সহজেই ডিভাইড-এন্ড-কনকার অ্যালগোরিদমের ধাপগুলো এভাবে মনে রাখতে পারবে ডিভাইড, কনকার, কম্বাইন। একটি ধাপে কীভাবে সমস্যাটি দেখা হয় সেটা হল, মনে করা যাক ডিভাইডের প্রতিটি ধাপ দুইটি করে ছোট সমস্যা তৈরি করে (যদিও কিছু কিছু ডিভাইড-এন্ড-কনকার অ্যালগোরিদম দুইটির বেশি সমস্যা তৈরি করে থাকে):
আমরা যদি আরও দুইটি পুনরাবৃত্তির ধাপে এটা বিস্তৃত করি, তাহলে এটা দেখতে এমন হবে:
কারণ ডিভাইড-এন্ড-কনকার কমপক্ষে দুইটি ছোট সমস্যা তৈরি করে থাকে, একটি ডিভাইড-এন্ড-কনকার অ্যালগোরিদম কয়েকটি পুনরাবৃত্তিমূলক কল তৈরি করে থাকে।
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।