ডিভাইড এন্ড কনকার একটি সমস্যা সমাধান করে (১) এটিকে ছোট সাব-প্রবলেমে বিভক্ত করে, (২) প্রতিটিকে রিকার্সিভভাবে জয় করে, এবং (৩) ফলাফল সংযুক্ত করে। অনেক দক্ষ অ্যালগরিদম এই টেমপ্লেট অনুসরণ করে।
যদি সাব-প্রবলেমগুলি স্বাধীন হয় এবং দ্রুত সংকুচিত হয়, তাহলে মোট কাজ একটি রিকারেন্স অনুসরণ করে যা আপনি মাস্টার থিওরেম দিয়ে বিশ্লেষণ করতে পারেন।
def max_dc(arr, lo, hi):
if lo == hi: # base case: one element
return arr[lo]
mid = (lo + hi) // 2
left = max_dc(arr, lo, mid) # conquer left
right = max_dc(arr, mid + 1, hi) # conquer right
return max(left, right) # combine
max_dc([3, 9, 2, 7], 0, 3) # -> 9
সাধারণত T(n) = a·T(n/b) + f(n); মার্জ সর্টের জন্য, T(n) = 2T(n/2) + O(n) = O(n log n)।
ব্যবহার করুন যখন একটি সমস্যা পরিষ্কারভাবে স্বাধীন সাব-প্রবলেমে বিভক্ত হয়। যদি সাব-প্রবলেমগুলি ওভারল্যাপ করে, তাহলে পরিবর্তে ডায়নামিক প্রোগ্রামিং পছন্দ করুন (পুনর্গণনা এড়াতে)। রিকার্সন ওভারহেড এবং কম্বাইন স্টেপ ছোট ইনপুটের জন্য প্রভাবশালী হতে পারে।
ডিভাইড এন্ড কনকার হল দক্ষ অ্যালগরিদমের বিশাল অংশের পিছনে একটি পুনঃব্যবহারযোগ্য ব্লুপ্রিন্ট।
প্যাটার্ন চেনা আপনাকে রিকারেন্স দিয়ে দ্রুত নতুন অ্যালগরিদম তৈরি এবং বিশ্লেষণ করতে দেয়।
এটি প্যারালেলিজমের সাথেও স্বাভাবিকভাবে ম্যাপ করে, কারণ স্বাধীন সাব-প্রবলেমগুলি একযোগে চলতে পারে।
বিস্তারিত উত্তরসহ IT ইন্টারভিউ প্রশ্নের একটি লাইব্রেরি — জুনিয়র থেকে সিনিয়র পর্যন্ত।
দান করুন