ডিভাইড এন্ড কনকার (Divide and Conquer) পদ্ধতি হল একটি শক্তিশালী অ্যালগরিদম ডিজাইন প্যাটার্ন, যেখানে সমস্যা সমাধানের জন্য বড় সমস্যাকে ছোট ছোট অংশে ভাগ করা হয়। এই পদ্ধতি মূলত তিনটি ধাপে কাজ করে:
- Divide (ভাগ করা): বড় সমস্যাটিকে ছোট ছোট সাব-প্রব্লেমে ভাগ করা হয়।
- Conquer (দখল করা): প্রত্যেক সাব-প্রব্লেমকে রিকার্সিভলি সমাধান করা হয়।
- Combine (একত্রিত করা): প্রতিটি সাব-প্রব্লেমের সমাধান একত্রিত করে আসল সমস্যার সমাধান পাওয়া যায়।
এই পদ্ধতিটি সাধারণত রিকার্সন ব্যবহার করে এবং এটি কার্যক্ষম এবং দ্রুত সমাধান পেতে অনেক ক্ষেত্রে বেশ কার্যকর।
ডিভাইড এন্ড কনকার-এর সুবিধা
- বড় ও জটিল সমস্যাকে ছোট ছোট উপ-সমস্যায় বিভক্ত করে সমাধান করা সহজ হয়।
- টাইম কমপ্লেক্সিটি কমানো যায়।
- বৃহৎ ইনপুটের ক্ষেত্রে কার্যকর।
ডিভাইড এন্ড কনকার পদ্ধতির অ্যাপ্লিকেশন
১. মার্জ সর্ট (Merge Sort)
Merge Sort একটি Divide and Conquer ভিত্তিক সর্টিং অ্যালগরিদম যা তালিকাকে ক্রমবর্ধমান বা ক্রমহ্রাসমান ক্রমে সর্ট করতে ব্যবহৃত হয়। এতে তালিকাটি বারবার দুই ভাগে বিভক্ত করা হয় এবং প্রতিটি উপ-তালিকাকে সর্ট করে একত্রিত করা হয়।
টাইম কমপ্লেক্সিটি: O(n log n)
প্রক্রিয়া:
- তালিকাটি বারবার দুটি ভাগে বিভক্ত করা হয় যতক্ষণ না একক উপাদানের সাব-তালিকা পাওয়া যায়।
- প্রতিটি সাব-তালিকাকে ক্রমান্বয়ে মিলিয়ে সর্ট করা হয়।
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
২. কুইক সর্ট (Quick Sort)
Quick Sort ডিভাইড এন্ড কনকার পদ্ধতিতে নির্মিত আরেকটি সর্টিং অ্যালগরিদম। এটি একটিকে পিভট হিসেবে বেছে নেয় এবং সেই পিভটের চেয়ে ছোট ও বড় উপাদানগুলোকে দুই ভাগে ভাগ করে।
টাইম কমপ্লেক্সিটি: গড়ে O(n log n), তবে Worst Case O(n^2)
প্রক্রিয়া:
- একটি পিভট নির্বাচন করা হয়।
- পিভটের চেয়ে ছোট উপাদান বাম দিকে এবং বড় উপাদান ডান দিকে সরিয়ে বিভক্ত করা হয়।
- প্রতিটি অংশে একই পদ্ধতি পুনরায় চালানো হয়।
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
৩. বাইনারি সার্চ (Binary Search)
বাইনারি সার্চ একটি Divide and Conquer ভিত্তিক সার্চিং অ্যালগরিদম যা কেবলমাত্র বিন্যস্ত তালিকার উপর কাজ করে। এটি ইনপুট তালিকাকে দুই ভাগে ভাগ করে এবং প্রতিটি ভাগে অনুসন্ধান করে।
টাইম কমপ্লেক্সিটি: O(log n)
প্রক্রিয়া:
- তালিকার মধ্য বিন্দু খুঁজে বের করা হয়।
- মধ্য বিন্দুর উপাদানটি অনুসন্ধানযোগ্য উপাদানের সমান হলে অনুসন্ধান সফল হয়।
- যদি না হয় তবে পজিশন অনুযায়ী ডান বা বাম অংশে অনুসন্ধান চালানো হয়।
def binary_search(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
৪. ফাস্ট ফুরিয়ার ট্রান্সফর্ম (FFT - Fast Fourier Transform)
FFT একটি Divide and Conquer ভিত্তিক অ্যালগরিদম যা সিগন্যাল প্রসেসিং, ইমেজ প্রক্রিয়াকরণ, এবং ডেটা কমপ্রেশনে ব্যবহৃত হয়। এটি ডেটাকে ছোট ছোট অংশে ভাগ করে এবং প্রতিটি অংশে দ্রুত ফুরিয়ার ট্রান্সফর্ম প্রয়োগ করে।
৫. ম্যাট্রিক্স মাল্টিপ্লিকেশন (Matrix Multiplication - Strassen’s Algorithm)
Strassen’s Algorithm একটি উন্নত ম্যাট্রিক্স মাল্টিপ্লিকেশন পদ্ধতি, যা Divide and Conquer পদ্ধতি ব্যবহার করে ম্যাট্রিক্সকে ছোট সাব-ম্যাট্রিক্সে ভাগ করে মুলতুবাকৃত ফলাফল দ্রুত বের করে।
টাইম কমপ্লেক্সিটি: O(n^2.81) (যা সাধারণ O(n^3) ম্যাট্রিক্স মুলতুবাকরণের চেয়ে কার্যকর)
সারসংক্ষেপ
ডিভাইড এন্ড কনকার পদ্ধতি বিভিন্ন সমস্যার সমাধান দ্রুত ও কার্যকরভাবে করতে সহায়ক। বড় বড় সমস্যাগুলিকে ছোট ছোট উপ-সমস্যায় বিভক্ত করে এবং প্রতিটি সমস্যার সমাধান একত্রিত করে পূর্ণ সমাধান পাওয়া যায়।
Read more
