ডিভাইড এন্ড কনকার (Divide and Conquer)

ডিভাইড এন্ড কনকার (Divide and Conquer) হল একটি জনপ্রিয় অ্যালগরিদমিক কৌশল, যা একটি বড় সমস্যা ছোট ছোট উপ-সমস্যায় ভাগ করে এবং প্রতিটি উপ-সমস্যার সমাধান করে শেষে তাদের একত্রিত (combine) করে মূল সমস্যার সমাধান করে। এই পদ্ধতিটি অনেক সমস্যায় কার্যকর, যেমন সর্টিং অ্যালগরিদম (Sorting Algorithms), সার্চিং অ্যালগরিদম (Searching Algorithms) এবং ম্যাট্রিক্স ম্যানিপুলেশন (Matrix Manipulation)।

ডিভাইড এন্ড কনকার অ্যালগরিদমের তিনটি প্রধান ধাপ থাকে:

1. ডিভাইড (Divide): সমস্যাটিকে ছোট ছোট উপ-সমস্যায় ভাগ করা।
2. কনকার (Conquer): প্রতিটি উপ-সমস্যার সমাধান করা। যদি উপ-সমস্যা আরও ছোট হয়ে যায়, তবে আবার সেগুলিকে বিভক্ত করা হয়।
3. কমবাইন (Combine): উপ-সমস্যাগুলোর সমাধান একত্রিত করে মূল সমস্যার সমাধান তৈরি করা।

ডিভাইড এন্ড কনকার অ্যালগরিদমের দুটি উদাহরণ খুব জনপ্রিয়: মার্জ সর্ট (Merge Sort) এবং কুইক সর্ট (Quick Sort)।

1. মার্জ সর্ট (Merge Sort)

মার্জ সর্ট (Merge Sort) একটি ডিভাইড এন্ড কনকার অ্যালগরিদম, যা একটি অ্যারেকে দুইটি সমান অংশে ভাগ করে এবং পরে প্রতিটি অংশকে পুনরায় মার্জ করে সাজায়। এটি একটি স্টেবল সর্টিং অ্যালগরিদম, যেখানে প্রতিটি উপাংশকে সাজানোর পর সেই দুইটি অংশকে একত্রিত করে পুরো অ্যারে সাজানো হয়।

সময় জটিলতা (Time Complexity): $O(n \log n)$

মার্জ সর্টের জাভা ইমপ্লিমেন্টেশন:

public class MergeSort {

    // Method to merge two subarrays into a sorted array
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Temporary arrays to hold the split arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays L[] and R[]
        System.arraycopy(arr, left, L, 0, n1);
        System.arraycopy(arr, mid + 1, R, 0, n2);

        int i = 0, j = 0;
        int k = left;
        
        // Merge the temporary arrays back into arr[]
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[], if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy remaining elements of R[], if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Method to implement the merge sort
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Divide the array into two halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the two halves
            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        
        // Call merge sort
        mergeSort(arr, 0, arr.length - 1);
        
        // Print the sorted array
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

আউটপুট:

Sorted array: 
3 9 10 27 38 43 82

এখানে, mergeSort() মেথডটি অ্যারেটি দুইটি অংশে ভাগ করে এবং তারপর merge() মেথডের মাধ্যমে দুইটি সজ্জিত অংশ একত্রিত করে পুরো অ্যারেটি সাজায়।

2. কুইক সর্ট (Quick Sort)

কুইক সর্ট (Quick Sort) একটি অন্য ধরনের ডিভাইড এন্ড কনকার অ্যালগরিদম, যা পিভট (pivot) ব্যবহার করে একটি অ্যারে সাজায়। এটি একটি খুবই কার্যকরী অ্যালগরিদম যা অ্যারের এলিমেন্টগুলিকে দুটি গ্রুপে ভাগ করে (পিভট থেকে ছোট এবং পিভট থেকে বড়), এবং পরে প্রতিটি গ্রুপে আবার কুইক সর্ট প্রয়োগ করা হয়।

সময় জটিলতা (Time Complexity): $O(n \log n)$ (গড় ক্ষেত্রে), $O(n^2)$ (খারাপ ক্ষেত্রে)

কুইক সর্টের জাভা ইমপ্লিমেন্টেশন:

public class QuickSort {

    // Method to partition the array
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Pivot element
        int i = (low - 1); // Index of smaller element

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i + 1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    // Method to implement quicksort
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partitioning index, arr[p] is now at right place
            int pi = partition(arr, low, high);

            // Recursively sort the elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        
        // Call quicksort
        quickSort(arr, 0, arr.length - 1);
        
        // Print the sorted array
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

আউটপুট:

Sorted array: 
1 5 7 8 9 10 

এখানে, quickSort() মেথডটি পিভট নির্বাচন করে এবং অ্যারেটি দুইটি অংশে ভাগ করে, তারপর ওই অংশগুলিতে পুনরায় কুইক সর্ট প্রয়োগ করে।

ডিভাইড এন্ড কনকারের সুবিধা

1. কার্যকারিতা (Efficiency): অনেক ক্ষেত্রে, ডিভাইড এন্ড কনকার অ্যালগরিদমগুলো অত্যন্ত দক্ষ হয়, যেমন মার্জ সর্ট এবং কুইক সর্ট যার সময় জটিলতা গড় ক্ষেত্রে $O(n \log n)$ হয়।
2. সমস্যা বিভাজন (Problem Dividing): যেকোনো বড় সমস্যা ছোট ছোট সমস্যায় ভাগ করা যায়, যা সমাধান করতে সহজ হয়।
3. পারালাল প্রসেসিং (Parallel Processing): ডিভাইড এন্ড কনকার অ্যালগরিদমগুলো সহজেই পারালালভাবে সম্পাদিত হতে পারে।

ডিভাইড এন্ড কনকারের অসুবিধা

1. কমপ্লেক্সিটি (Complexity): কিছু ক্ষেত্রে, এই অ্যালগরিদমগুলো কোডে জটিলতা সৃষ্টি করতে পারে এবং ডিবাগিং করা কঠিন হতে পারে।
2. স্ট্যাক মেমরি ব্যবহার (Stack Memory Usage): রিকর্শন ব্যবহার করলে অতিরিক্ত স্ট্যাক মেমরি ব্যবহার হয়, বিশেষ করে খারাপ কেসে কুইক সর্টের জন্য।

সারাংশ

ডিভাইড এন্ড কনকার (Divide and Conquer) একটি শক্তিশালী অ্যালগরিদমিক কৌশল যা একটি বড় সমস্যা ছোট ছোট উপ-সমস্যায় ভাগ করে সমাধান করা হয়। মার্জ সর্ট এবং কুইক সর্ট এই কৌশলের দুটি জনপ্রিয় উদাহরণ। এই পদ্ধতিটি সমস্যা সমাধানে কার্যকরী এবং অনেক ক্ষেত্রে $O(n \log n)$ সময় জটিলতা প্রদান করে।

Divide and Conquer

Divide and Conquer হল একটি অ্যালগরিদমিক কৌশল যা একটি বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় বিভক্ত করে এবং প্রতিটি উপ-সমস্যার সমাধান করে, তারপর তাদের একত্রিত করে মূল সমস্যার সমাধান পাওয়া যায়। এই কৌশলটি বেশিরভাগ কার্যকরী অ্যালগরিদমে ব্যবহৃত হয়, যেমন Merge Sort এবং Quick Sort।

Divide and Conquer পদ্ধতির তিনটি প্রধান ধাপ:

1. Divide: সমস্যাটিকে ছোট ছোট উপ-সমস্যায় বিভক্ত করা।
2. Conquer: প্রতিটি উপ-সমস্যা সমাধান করা।
3. Combine: উপ-সমস্যাগুলির সমাধান একত্রিত করা।

1. Merge Sort

Merge Sort একটি Divide and Conquer অ্যালগরিদম যা একটি অ্যারে বা তালিকাকে বিভক্ত করে এবং প্রতিটি ভাগকে সজ্জিত করে, তারপর ঐ সমস্ত ভাগগুলোকে একত্রিত করে সাজানো (merge) করে। এটি একটি Stable Sorting Algorithm এবং এটি সর্বদা O(n log n) টাইম কমপ্লেক্সিটিতে কাজ করে, যা এটি একটি দক্ষ সাজানো অ্যালগরিদম বানায়।

Merge Sort এর প্রধান স্টেপ:

1. অ্যারেটি মাঝখানে ভাগ করুন (Divide).
2. প্রতিটি ভাগকে সজ্জিত করুন (Conquer).
3. সজ্জিত ভাগগুলোকে একত্রিত করুন (Combine).

Merge Sort Implementation:

public class MergeSort {
    // Method to merge two halves
    public static void merge(int[] arr, int left, int mid, int right) {
        // Find the size of two subarrays to be merged
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to temp arrays leftArray[] and rightArray[]
        System.arraycopy(arr, left, leftArray, 0, n1);
        System.arraycopy(arr, mid + 1, rightArray, 0, n2);

        // Merge the temp arrays back into arr[]
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // Copy any remaining elements of leftArray[]
        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        // Copy any remaining elements of rightArray[]
        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    // Method to sort the array using merge sort
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Recursively divide the array into two halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Unsorted Array:");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted Array using Merge Sort:");
        printArray(arr);  // Output: 3 9 10 27 38 43 82
    }
}

ব্যাখ্যা:

• merge: দুইটি সজ্জিত অংশকে একত্রিত (merge) করে একটি সজ্জিত অংশ তৈরি করে।
• mergeSort: এটি রিকার্সিভভাবে অ্যারেটি দুই ভাগে ভাগ করে এবং পরবর্তীতে তাদেরকে সজ্জিত করে।
• Time Complexity: O(n log n) - এখানে n হল অ্যারের সাইজ এবং log n হল বিভাজনের স্তর সংখ্যা।

2. Quick Sort

Quick Sort একটি Divide and Conquer অ্যালগরিদম যা একে একে এলিমেন্টগুলোকে এমনভাবে ভাগ করে যে প্রতিটি ভাগে একটির চেয়ে বড় এবং একটির চেয়ে ছোট উপাদান থাকবে। এটি "partitioning" কৌশল ব্যবহার করে এবং সবচেয়ে দক্ষ সাজানো অ্যালগরিদমগুলোর মধ্যে একটি।

Quick Sort এর প্রধান স্টেপ:

1. একটি পিভট নির্বাচন করুন (এটি সাধারণত অ্যারের প্রথম, শেষ, বা মাঝখানের উপাদান হতে পারে)।
2. অ্যারের উপাদানগুলো এমনভাবে সজ্জিত করুন যাতে পিভটের বাম দিকে ছোট উপাদান এবং ডান দিকে বড় উপাদান থাকে।
3. পুনরায় সাব-অ্যারেগুলির উপর Quick Sort প্রয়োগ করুন।

Quick Sort Implementation:

public class QuickSort {
    // Method to perform partitioning
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // Choosing the last element as pivot
        int i = (low - 1);  // Index of smaller element

        // Re-arrange elements
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i+1] and arr[high] (pivot element)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;  // Return the pivot index
    }

    // Method to implement quick sort
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array
            int pi = partition(arr, low, high);

            // Recursively sort the sub-arrays
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Unsorted Array:");
        printArray(arr);

        quickSort(arr, 0, arr.length - 1);

        System.out.println("Sorted Array using Quick Sort:");
        printArray(arr);  // Output: 3 9 10 27 38 43 82
    }
}

ব্যাখ্যা:

• partition: এটি একটি পিভট নির্বাচন করে এবং অ্যারের উপাদানগুলোকে পিভটের তুলনায় ছোট এবং বড় উপাদানে ভাগ করে।
• quickSort: এটি রিকার্সিভভাবে অ্যারের দুটি ভাগে (পিভটের বাম এবং ডান) Quick Sort প্রয়োগ করে।
• Time Complexity: O(n log n) (গড় ক্ষেত্রে), তবে worst case O(n²) হতে পারে যদি পিভট সঠিকভাবে নির্বাচিত না হয়।

3. Merge Sort vs Quick Sort

সারাংশ

Merge Sort এবং Quick Sort হল দুটি জনপ্রিয় Divide and Conquer অ্যালগরিদম যা দ্রুত এবং কার্যকরীভাবে ডেটা সজ্জিত করতে ব্যবহৃত হয়।

• Merge Sort একটি স্টেবল অ্যালগরিদম যা সর্বদা O(n log n) টাইম কমপ্লেক্সিটিতে কাজ করে, তবে এটি অতিরিক্ত মেমরি ব্যবহার করে।
• Quick Sort সাধারণত দ্রুত কাজ করে, কিন্তু O(n²) হতে পারে যদি পিভট সঠিকভাবে নির্বাচিত না হয়। এটি ইনপ্লেস কাজ করে, অর্থাৎ অতিরিক্ত মেমরি ব্যবহারের প্রয়োজন পড়ে না।

Divide and Conquer একটি শক্তিশালী অ্যালগরিদমিক কৌশল যা কোনো বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় বিভক্ত করে এবং তারপর সেই উপ-সমস্যাগুলির সমাধান একত্রিত করে। এই পদ্ধতিতে, আমরা প্রথমে একটি সমস্যাকে দুটি বা তার বেশি ছোট উপ-সমস্যায় ভাগ করি, তারপর সেই উপ-সমস্যাগুলির সমাধান করি এবং সবশেষে তাদের সমাধান একত্রিত করে মূল সমস্যার সমাধান পেয়ে যাই। Merge Sort এবং Quick Sort দুটি জনপ্রিয় অ্যালগরিদম যা Divide and Conquer পদ্ধতিতে কাজ করে।

Merge Sort

Merge Sort একটি কার্যকরী Divide and Conquer অ্যালগরিদম যা একটি অ্যারে বা তালিকা সন্নিবেশ করতে ব্যবহার করা হয়। এটি অ্যারের মাঝখানে বিভক্ত করে, তারপর প্রতিটি ভাগের উপাদানগুলোকে সন্নিবেশিতভাবে একত্রিত (merge) করে সম্পূর্ণ অ্যারে সাজানোর কাজ করে।

Merge Sort এর ধাপ:

1. অ্যারেটি মাঝখানে ভাগ করা হয়।
2. প্রতিটি ভাগকে আবার ভাগ করা হয় যতক্ষণ না অ্যারের মধ্যে একক উপাদান (1 element) থাকে।
3. পরে, ছোট ছোট অ্যারের উপাদানগুলো একত্রিত হয়ে সাজানো অ্যারে তৈরি হয়।

সময় জটিলতা:

• Worst-case time complexity: O(n log n)
• Best-case time complexity: O(n log n)
• Space complexity: O(n)

উদাহরণ:

public class MergeSort {

    // Merge Sort function
    public static void mergeSort(int[] arr) {
        if (arr.length < 2) return;

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        // Copy elements into left and right sub-arrays
        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        // Recursively sort both halves
        mergeSort(left);
        mergeSort(right);

        // Merge the sorted halves
        merge(arr, left, right);
    }

    // Merge function to combine two sorted sub-arrays
    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // Merge the two arrays into the original array
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        // Copy remaining elements from left or right
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Merge Sort এর কার্যকারিতা:

1. mergeSort() ফাংশনটি অ্যারেটিকে দুটি ভাগে বিভক্ত করে।
2. merge() ফাংশনটি দুইটি সাজানো অ্যারে (left এবং right) একত্রিত করে একটি নতুন সাজানো অ্যারে তৈরি করে।

Quick Sort

Quick Sort হল আরেকটি জনপ্রিয় Divide and Conquer অ্যালগরিদম যা একটি এলিমেন্টকে (pivot) নির্বাচন করে তার চারপাশের এলিমেন্টগুলোকে বিভক্ত করে। এটি এমনভাবে কাজ করে যে পিভট উপাদানের ডান দিকে থাকা সব উপাদান পিভটের চেয়ে বড় এবং বাম দিকে থাকা সব উপাদান পিভটের চেয়ে ছোট থাকে। এরপর এই প্রক্রিয়াটি প্রতিটি ভাগের জন্য পুনরায় করা হয়।

Quick Sort এর ধাপ:

1. একটি পিভট উপাদান নির্বাচন করা হয় (সাধারণত শেষ বা প্রথম উপাদান নির্বাচন করা হয়)।
2. অ্যারের এলিমেন্টগুলোকে পিভটের চারপাশে সজ্জিত করা হয়।
3. দুটি সাব-অ্যারেতে পুনরায় Quick Sort প্রক্রিয়া চালানো হয়।

সময় জটিলতা:

• Worst-case time complexity: O(n^2) (যখন পিভট সবচেয়ে খারাপভাবে নির্বাচন করা হয়)
• Best-case time complexity: O(n log n)
• Average-case time complexity: O(n log n)
• Space complexity: O(log n) (স্ট্যাকের গভীরতা)

উদাহরণ:

public class QuickSort {

    // QuickSort function
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Find pivot element
            int pivotIndex = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // Partition function to rearrange elements around pivot
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i+1] and arr[high] (pivot element)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // Return the partition index
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Quick Sort এর কার্যকারিতা:

1. quickSort() ফাংশনটি অ্যারে ভাগ করে পিভটের চারপাশে সজ্জিত করে, তারপর দুইটি সাব অ্যারেতে পুনরায় Quick Sort চালায়।
2. partition() ফাংশনটি পিভট এলিমেন্ট নির্বাচন করে এবং তার চারপাশের এলিমেন্টগুলোকে সঠিক অবস্থানে রেখে পিভটের সঠিক স্থান নির্ধারণ করে।

Merge Sort এবং Quick Sort এর মধ্যে পার্থক্য

সারাংশ

Merge Sort এবং Quick Sort দুটি জনপ্রিয় Divide and Conquer অ্যালগরিদম যা বড় ডেটা সেটে দ্রুত সোর্টিং করতে ব্যবহৃত হয়। Merge Sort সার্বিকভাবে ধারাবাহিক এবং নিরাপদ, কারণ এটি সর্বদা O(n log n) সময়ে কাজ করে, তবে এটি অতিরিক্ত স্পেস প্রয়োজন করে। অন্যদিকে, Quick Sort সাধারণত দ্রুত, তবে খারাপ পিভট নির্বাচনের কারণে এর O(n^2) সময় জটিলতা হতে পারে, তবে সাধারণভাবে এটি O(n log n) সময়ে কাজ করে এবং কম স্পেস ব্যবহার করে। দুইটি অ্যালগরিদমই ডেটা সজ্জিত করতে কার্যকর, তবে তাদের ব্যবহার পরিস্থিতির উপর নির্ভর করে।

Binary Search হল একটি খুবই কার্যকরী অ্যালগরিদম যা sorted array বা sorted list তে একটি উপাদান দ্রুত খুঁজে বের করার জন্য ব্যবহৃত হয়। এটি একটি divide and conquer অ্যালগরিদম, যা প্রতিটি পদক্ষেপে সম্ভাব্য সন্ধানকৃত উপাদানকে অর্ধেক করে ভাগ করে, ফলে এটি খুব দ্রুত কাজ করে।

এটি O(log n) সময় কমপ্লেক্সিটির সাথে কাজ করে, যা সাধারণ linear search এর O(n) টাইম কমপ্লেক্সিটির চেয়ে অনেক বেশি দ্রুত।

1. Binary Search Algorithm

Binary Search কাজ করে sorted array বা sorted list তে যেখানে গড় মান (middle element) এর সাথে তুলনা করে উপাদানটি খোঁজা হয়। এর মৌলিক পদক্ষেপ:

1. Middle Element: প্রথমে সোজা middle element নির্বাচন করা হয়।
2. Comparison: যদি middle element আপনার খুঁজে পাওয়া উপাদান হয়, তবে আপনি খুঁজে পেয়েছেন।
3. Left or Right Subarray: যদি middle element থেকে ছোট বা বড় মান খুঁজতে হয়, তবে আপনি array এর বাম বা ডান অংশে চলে যান এবং পুনরায় একই প্রক্রিয়া চালিয়ে যান।

2. Binary Search Algorithm Steps

1. Start with the full array and find the middle element.
2. If the middle element matches the target, return its index.
3. If the target is smaller than the middle element, repeat the search on the left half of the array.
4. If the target is larger than the middle element, repeat the search on the right half of the array.
5. If the element is not found, return a value indicating it’s not present (commonly -1).

3. Binary Search Example in Java

3.1. Recursive Binary Search Implementation

public class BinarySearch {

    // Recursive function to perform binary search
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // Element not found
        }

        int mid = left + (right - left) / 2;

        // Check if target is present at mid
        if (arr[mid] == target) {
            return mid; // Target found at mid
        }

        // If target is smaller than mid, search in the left subarray
        if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        }

        // If target is larger than mid, search in the right subarray
        return binarySearch(arr, mid + 1, right, target);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;

        int result = binarySearch(arr, 0, arr.length - 1, target);

        if (result == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

ব্যাখ্যা:

• binarySearch() ফাংশনটি রিকার্সিভভাবে left এবং right পয়েন্টার ব্যবহার করে মধ্যবর্তী উপাদান খুঁজে বের করে এবং তাকে টার্গেটের সাথে তুলনা করে।
• Base Case: যদি left > right হয়, তাহলে এটি দেখায় যে উপাদানটি খুঁজে পাওয়া যায়নি।
• Recursive Case: উপাদান পাওয়া না গেলে left বা right সাবঅ্যারে রিকার্সিভ কল করা হয়।

আউটপুট:

Element found at index: 3

3.2. Iterative Binary Search Implementation

public class BinarySearch {

    // Iterative function to perform binary search
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid; // Target found at mid
            }

            // If target is smaller than mid, search in the left subarray
            if (arr[mid] > target) {
                right = mid - 1;
            }
            // If target is larger than mid, search in the right subarray
            else {
                left = mid + 1;
            }
        }

        return -1; // Element not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;

        int result = binarySearch(arr, target);

        if (result == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

ব্যাখ্যা:

• Iterative Binary Search তে while লুপ ব্যবহার করা হয়েছে যেখানে left এবং right পয়েন্টার দ্বারা পুরো অ্যারে পার করে যাচ্ছি। যতক্ষণ না left পয়েন্টার right এর থেকে ছোট থাকে, ততক্ষণ লুপটি চলবে।
• এই পদ্ধতিতে রিকার্সন নেই, এবং এটি সাধারণত মেমরি ব্যবহারে সাশ্রয়ী।

আউটপুট:

Element found at index: 3

4. Time Complexity of Binary Search

• Time Complexity:
  • Best Case: O(1) (যখন প্রথমেই middle element হলো টার্গেট)
  • Worst Case: O(log n) (এটি প্রতি পদক্ষেপে ডাটা অর্ধেক করে কাটে)
  • Average Case: O(log n)
• Space Complexity:
  • Recursive Version: O(log n) (কারণ রিকার্সন কল স্ট্যাক)
  • Iterative Version: O(1) (কারণ লুপে কোনো অতিরিক্ত স্ট্যাকের প্রয়োজন হয় না)

5. Binary Search এর ব্যবহার

• Searching in Sorted Arrays: এটি sorted arrays বা sorted lists তে উপাদান খোঁজার জন্য ব্যবহৃত হয়।
• Efficient Search: একে দ্রুত searching এর জন্য ব্যবহৃত হতে পারে, যেখানে সাধারণ linear search অনেক ধীরে কাজ করে।
• Binary Search Tree (BST): এটি Binary Search Tree তে ব্যবহার হয় যেখানে প্রতিটি নোডের বাম দিকের মান ছোট এবং ডান দিকের মান বড় থাকে।

6. Binary Search with Matrix (2D array)

যখন আপনি 2D ম্যাট্রিক্সের মধ্যে বাইনারি সার্চ ব্যবহার করতে চান, তখন এটা সাধারণত row-wise বা column-wise সজ্জিত ম্যাট্রিক্সে কার্যকরী হয়। 2D ম্যাট্রিক্সের জন্য binary search বিভিন্ন কৌশল ব্যবহার করা যেতে পারে।

6.1. Binary Search in 2D Matrix Example

public class BinarySearch2D {
    public static boolean binarySearch2D(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        int left = 0, right = rows * cols - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / cols][mid % cols];

            if (midElement == target) {
                return true;
            } else if (midElement < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false; // Target not found
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 60}
        };
        int target = 3;

        boolean result = binarySearch2D(matrix, target);
        System.out.println("Element found: " + result);
    }
}

আউটপুট:

Element found: true

সারাংশ

Binary Search হল একটি অত্যন্ত কার্যকরী এবং দ্রুত অ্যালগরিদম, যা sorted array বা sorted list তে O(log n) সময়ে কোনো উপাদান খুঁজে বের করে। Recursive এবং Iterative উভয় পদ্ধতিতে binary search ব্যবহার করা যেতে পারে এবং উভয় পদ্ধতিরই সুবিধা ও অসুবিধা রয়েছে। Binary Search বিভিন্ন ক্ষেত্র যেমন 2D matrix, binary search tree (BST) এবং sorted arrays তে ব্যবহৃত হয় এবং এটি efficient searching এর জন্য অপরিহার্য একটি টুল।

Divide and Conquer (D&C) একটি শক্তিশালী প্রোগ্রামিং কৌশল যা একটি সমস্যা ছোট ছোট উপ-সমস্যায় বিভক্ত করে এবং প্রতিটি উপ-সমস্যা স্বাধীনভাবে সমাধান করার পর একত্রিত করে মূল সমস্যার সমাধান তৈরি করে। এই কৌশলটি সাধারণত recursive অ্যালগরিদমগুলিতে ব্যবহৃত হয়, এবং এটি অনেক ক্ষেত্রে efficient সমাধান প্রদান করে।

এখানে আমরা Divide and Conquer পদ্ধতির Time Complexity (সময় জটিলতা) এবং Space Complexity (স্থান জটিলতা) নিয়ে আলোচনা করব। সাধারণভাবে, Divide and Conquer অ্যালগরিদমগুলির সময় ও স্থান জটিলতা বিশ্লেষণ করার জন্য Recurrence Relation ব্যবহৃত হয়।

1. Divide and Conquer কৌশল

Divide and Conquer মূলত তিনটি প্রধান ধাপে কাজ করে:

1. Divide: সমস্যা দুটি বা তার বেশি ছোট উপ-সমস্যায় ভাগ করা হয়।
2. Conquer: প্রতিটি উপ-সমস্যার সমাধান করা হয় (সাধারণত রিকার্সিভভাবে)।
3. Combine: উপ-সমস্যাগুলির সমাধান একত্রিত করে মূল সমস্যার সমাধান তৈরি করা হয়।

Example: একটি ক্লাসিক্যাল Divide and Conquer অ্যালগরিদম হল Merge Sort, যেখানে একটি অ্যারের এলিমেন্টগুলি দুটি ভাগে বিভক্ত করা হয় এবং তারপর প্রতিটি ভাগ সজ্জিত করা হয়।

2. Recurrence Relation

Recurrence Relation হলো একটি সমীকরণ যা অ্যালগরিদমের সময়ে বা স্থানে কার্যকরভাবে বৃদ্ধি (growth) নির্ধারণ করে। Divide and Conquer অ্যালগরিদমগুলির সময় জটিলতা সাধারণত একটি রিকার্সিভ সমীকরণ হিসাবে প্রকাশ করা হয়।

যেমন, যদি একটি সমস্যা n আকারের হয়, এবং এটি দুটি ছোট উপ-সমস্যায় বিভক্ত হয় যার প্রতিটির আকার n/2, এবং সমাধান করার জন্য O(n) কাজ লাগে (তথ্য সংকলন বা একত্রিতকরণের জন্য), তবে সেই অ্যালগরিদমের recurrence relation হবে:

$$T(n) = 2T(n/2) + O(n)$$

এখানে:

• 2T(n/2): উপ-সমস্যাগুলির সমাধান।
• O(n): সমাধানগুলির একত্রিতকরণের সময়।

এই সমীকরণটির ভিত্তিতে, আমরা অ্যালগরিদমের time complexity এবং space complexity বের করতে পারি।

3. Time Complexity (সময় জটিলতা)

Divide and Conquer অ্যালগরিদমের সময় জটিলতা নির্ধারণ করতে Master Theorem ব্যবহার করা হয়। এটি একটি সোজা উপায় যা recurrence relation সমাধান করতে সাহায্য করে। যদি আমাদের recurrence relation এমনভাবে থাকে:

$$T(n) = aT(n/b) + O(n^d)$$

এখানে:

• a: উপ-সমস্যার সংখ্যা।
• n/b: উপ-সমস্যার আকার।
• n^d: একত্রিতকরণের কাজের সময়।

Master Theorem অনুযায়ী, T(n) এর সময় জটিলতা তিনটি ক্ষেত্রে বিভক্ত:

1. Case 1 (If $a < b^d$):
   • Time Complexity: $O(n^d)$
   • Explanation: যখন উপ-সমস্যাগুলির সংখ্যা কম এবং তাদের আকারের বৃদ্ধি দ্রুত হয়, তখন একত্রিতকরণের কাজের সময় প্রধান হয়ে ওঠে।
2. Case 2 (If $a = b^d$):
   • Time Complexity: $O(n^d \log n)$
   • Explanation: এখানে, সমানভাবে উপ-সমস্যাগুলির সংখ্যা এবং আকারের বৃদ্ধির কারণে, একত্রিতকরণের কাজ এবং পুনরাবৃত্তি কাজের মধ্যে ব্যালান্স থাকে।
3. Case 3 (If $a > b^d$):
   • Time Complexity: $O(n^{\log_b a})$
   • Explanation: যখন উপ-সমস্যাগুলির সংখ্যা বেশি এবং আকারের বৃদ্ধি কম, তখন উপ-সমস্যাগুলির সমাধান টাইম ডমিনেট করবে।

3.1. Time Complexity Example - Merge Sort

Merge Sort একটি ক্লাসিক Divide and Conquer অ্যালগরিদম, যা রিকার্সিভভাবে অ্যারেকে দুটি সমান অংশে ভাগ করে এবং প্রতিটি অংশে Merge অপারেশন ব্যবহার করে একত্রিত করে।

Recurrence Relation for Merge Sort:

$$T(n) = 2T(n/2) + O(n)$$

এই সমীকরণে:

• $a = 2$: দুটি উপ-সমস্যায় ভাগ হচ্ছে।
• $b = 2$: প্রতিটি উপ-সমস্যার আকার $n/2$।
• $d = 1$: একত্রিতকরণের কাজের জন্য O(n)।

এটি Case 2 এর মধ্যে পড়ে, যেখানে $a = b^d$, সুতরাং:

$$T(n) = O(n \log n)$$

এবং তাই Merge Sort এর সময় জটিলতা হল O(n log n)।

4. Space Complexity (স্থান জটিলতা)

Space Complexity এর মধ্যে মূলত দুটি উপাদান থাকে:

1. Auxiliary Space: অতিরিক্ত স্থান যা অ্যালগরিদম চলাকালীন ব্যবহৃত হয় (যেমন, স্ট্যাক স্পেস, টেম্পোরারি ডাটা স্ট্রাকচার ইত্যাদি)।
2. Input Space: ইনপুট ডাটা যতটুকু জায়গা নেবে।

4.1. Space Complexity Example - Merge Sort

Merge Sort এর মধ্যে রিকার্সিভ কল স্ট্যাক এবং সেকেন্ডারি অ্যারে ব্যবহার করা হয়। সুতরাং, এর auxiliary space এর জটিলতা হবে O(n), যেখানে n হল ইনপুটের সাইজ।

5. Time Complexity and Space Complexity Summary

Divide and Conquer কৌশল ব্যবহার করে সমস্যাগুলি ছোট ছোট উপ-সমস্যায় বিভক্ত করা হয় এবং তারপর সেগুলির সমাধান একত্রিত করা হয়। এই কৌশলটি merge sort, quick sort, binary search, এবং অন্যান্য অনেক অ্যালগরিদমে ব্যবহৃত হয়।

• Time Complexity নির্ধারণ করতে Recurrence Relation এবং Master Theorem ব্যবহৃত হয়।
• Merge Sort এবং অন্যান্য Divide and Conquer অ্যালগরিদমগুলির সাধারণ সময় জটিলতা হলো O(n log n), যেখানে space complexity সাধারণত O(n) হতে পারে।