Menganalisis kerumitan masa dan kerumitan ruang algoritma isihan pantas Java

Analisis kerumitan masa dan kerumitan ruang fungsi Java Quick Sort

Quick adalah algoritma penyortiran berasaskan perbandingan diisih secara individu sehingga keseluruhan tatasusunan diisih. Kerumitan masa dan kerumitan ruang isihan pantas adalah faktor utama yang perlu kita pertimbangkan apabila menggunakan algoritma pengisihan ini.

Idea asas isihan pantas ialah memilih elemen sebagai pangsi (pangsi), dan kemudian membahagikan elemen lain dalam tatasusunan kepada dua sub-tatasusunan berdasarkan hubungannya dengan unsur-unsur satu sub-tatasusunan adalah kurang daripada atau sama dengan pangsi, dan unsur-unsur sub-tatasusunan yang lain adalah kurang daripada atau sama dengan pangsi. Kedua-dua subarray kemudian diisih secara rekursif dan akhirnya digabungkan.

Berikut ialah contoh kod fungsi isihan pantas yang dilaksanakan dalam Java:

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high);
            quickSort(arr, low, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    public 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, j);
            }
        }

        swap(arr, i + 1, high);

        return i + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Kerumitan masa isihan pantas ialah O(nlogn), dengan n ialah panjang tatasusunan. Dalam kes terbaik, di mana setiap partition membahagikan tatasusunan dengan tepat sama, kerumitan masa isihan pantas ialah O(nlogn). Dalam kes yang paling teruk, iaitu, setiap partition mencari elemen terkecil atau terbesar tatasusunan sebagai elemen pangsi, kerumitan masa isihan pantas ialah O(n^2). Secara purata, kerumitan masa isihan pantas juga O(nlogn).

Kerumitan ruang isihan pantas ialah O(logn), dengan logn ialah kedalaman timbunan panggilan rekursif. Dalam kes terbaik, di mana setiap partition membahagikan tatasusunan dengan tepat sama, kerumitan ruang isihan pantas ialah O(logn). Dalam kes yang paling teruk, iaitu, setiap partition mencari elemen terkecil atau terbesar tatasusunan sebagai elemen pangsi, kerumitan ruang isihan pantas ialah O(n). Secara purata, kerumitan ruang bagi quicksort juga O(logn).

Perlu diingatkan bahawa kerumitan ruang isihan pantas merujuk kepada ruang tambahan yang diperlukan sebagai tambahan kepada tatasusunan input, dan tidak termasuk ruang tatasusunan input.

Ringkasnya, isihan pantas ialah algoritma pengisihan yang cekap dengan kerumitan masa dan kerumitan ruang yang rendah. Dalam aplikasi praktikal, walaupun kerumitan masa terburuk jenis cepat ialah O(n^2), purata kerumitan masa isihan pantas ialah O(nlogn), dan data dalam aplikasi praktikal adalah sangat kecil Senario kes terburuk adalah kurang berkemungkinan, jadi isihan pantas masih merupakan algoritma isihan pemilihan.

Atas ialah kandungan terperinci Menganalisis kerumitan masa dan kerumitan ruang algoritma isihan pantas Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!