Rumah Java javaTutorial Menganalisis kerumitan masa dan kerumitan ruang algoritma isihan pantas Java

Menganalisis kerumitan masa dan kerumitan ruang algoritma isihan pantas Java

Feb 25, 2024 am 11:39 AM

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 + " ");
        }
    }
}
Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Adakah perisian keselamatan syarikat menyebabkan aplikasi gagal dijalankan? Bagaimana cara menyelesaikan masalah dan menyelesaikannya? Adakah perisian keselamatan syarikat menyebabkan aplikasi gagal dijalankan? Bagaimana cara menyelesaikan masalah dan menyelesaikannya? Apr 19, 2025 pm 04:51 PM

Penyelesaian masalah dan penyelesaian kepada perisian keselamatan syarikat yang menyebabkan beberapa aplikasi tidak berfungsi dengan baik. Banyak syarikat akan menggunakan perisian keselamatan untuk memastikan keselamatan rangkaian dalaman. …

Bagaimana untuk memudahkan isu pemetaan medan dalam dok sistem menggunakan mapstruct? Bagaimana untuk memudahkan isu pemetaan medan dalam dok sistem menggunakan mapstruct? Apr 19, 2025 pm 06:21 PM

Pemprosesan pemetaan medan dalam dok sistem sering menemui masalah yang sukar ketika melaksanakan sistem dok: bagaimana untuk memetakan medan antara muka sistem dengan berkesan ...

Bagaimana dengan elegan mendapatkan nama pemboleh ubah kelas entiti untuk membina keadaan pertanyaan pangkalan data? Bagaimana dengan elegan mendapatkan nama pemboleh ubah kelas entiti untuk membina keadaan pertanyaan pangkalan data? Apr 19, 2025 pm 11:42 PM

Apabila menggunakan Mybatis-Plus atau Rangka Kerja ORM yang lain untuk operasi pangkalan data, sering diperlukan untuk membina syarat pertanyaan berdasarkan nama atribut kelas entiti. Sekiranya anda secara manual setiap kali ...

Bagaimanakah Idea IntelliJ mengenal pasti nombor port projek boot musim bunga tanpa mengeluarkan log? Bagaimanakah Idea IntelliJ mengenal pasti nombor port projek boot musim bunga tanpa mengeluarkan log? Apr 19, 2025 pm 11:45 PM

Mula musim bunga menggunakan versi IntelliJideaultimate ...

Bagaimanakah saya menukar nama kepada nombor untuk melaksanakan penyortiran dan mengekalkan konsistensi dalam kumpulan? Bagaimanakah saya menukar nama kepada nombor untuk melaksanakan penyortiran dan mengekalkan konsistensi dalam kumpulan? Apr 19, 2025 pm 11:30 PM

Penyelesaian untuk menukar nama kepada nombor untuk melaksanakan penyortiran dalam banyak senario aplikasi, pengguna mungkin perlu menyusun kumpulan, terutama dalam satu ...

Bagaimana cara menukar objek Java dengan selamat ke array? Bagaimana cara menukar objek Java dengan selamat ke array? Apr 19, 2025 pm 11:33 PM

Penukaran objek dan tatasusunan Java: Perbincangan mendalam tentang risiko dan kaedah penukaran jenis cast yang betul Banyak pemula Java akan menemui penukaran objek ke dalam array ...

Bagaimana dengan elegan mendapatkan syarat pertanyaan bangunan pembolehubah kelas entiti apabila menggunakan tkmybatis untuk pertanyaan pangkalan data? Bagaimana dengan elegan mendapatkan syarat pertanyaan bangunan pembolehubah kelas entiti apabila menggunakan tkmybatis untuk pertanyaan pangkalan data? Apr 19, 2025 pm 09:51 PM

Apabila menggunakan tkmybatis untuk pertanyaan pangkalan data, bagaimana dengan anggun mendapatkan nama pembolehubah kelas entiti untuk membina keadaan pertanyaan adalah masalah biasa. Artikel ini akan ...

Bagaimana cara menukar nama ke nombor untuk melaksanakan penyortiran dalam kumpulan? Bagaimana cara menukar nama ke nombor untuk melaksanakan penyortiran dalam kumpulan? Apr 19, 2025 pm 01:57 PM

Bagaimana cara menukar nama ke nombor untuk melaksanakan penyortiran dalam kumpulan? Apabila menyusun pengguna dalam kumpulan, sering kali perlu menukar nama pengguna ke dalam nombor supaya ia boleh berbeza ...

See all articles