Analyser la complexité temporelle et spatiale de l'algorithme de tri rapide Java

Analyse de la complexité temporelle et spatiale de la fonction de tri rapide Java

Quick Sort est un algorithme de tri basé sur la comparaison. Il divise un tableau en deux sous-tableaux, puis compare les deux sous-tableaux. triés individuellement jusqu'à ce que l'ensemble du tableau soit trié. La complexité temporelle et la complexité spatiale du tri rapide sont des facteurs clés que nous devons prendre en compte lors de l'utilisation de cet algorithme de tri.

L'idée de base du tri rapide est de sélectionner un élément comme pivot (pivot), puis de diviser les autres éléments du tableau en deux sous-tableaux en fonction de leur relation avec le pivot. sont inférieurs ou égaux au pivot, et les éléments de l'autre sous-tableau sont inférieurs ou égaux au pivot. Les éléments du sous-tableau sont tous supérieurs ou égaux à l'élément pivot. Les deux sous-tableaux sont ensuite triés de manière récursive et finalement fusionnés.

Ce qui suit est un exemple de code d'une fonction de tri rapide implémentée en 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 + " ");
        }
    }
}

La complexité temporelle du tri rapide est O(nlogn), où n est la longueur du tableau. Dans le meilleur des cas, où chaque partition divise le tableau exactement de manière égale, la complexité temporelle du tri rapide est O(nlogn). Dans le pire des cas, c'est-à-dire que chaque partition trouve l'élément le plus petit ou le plus grand du tableau comme élément pivot, la complexité temporelle du tri rapide est O(n^2). En moyenne, la complexité temporelle du tri rapide est également O(nlogn).

La complexité spatiale du tri rapide est O(logn), où logn est la profondeur de la pile d'appels récursifs. Dans le meilleur des cas, où chaque partition divise le tableau exactement de manière égale, la complexité spatiale du tri rapide est O(logn). Dans le pire des cas, c'est-à-dire que chaque partition trouve l'élément le plus petit ou le plus grand du tableau comme élément pivot, la complexité spatiale du tri rapide est O(n). En moyenne, la complexité spatiale du tri rapide est également O(logn).

Il convient de noter que la complexité spatiale du tri rapide fait référence à l'espace supplémentaire requis en plus du tableau d'entrée, et n'inclut pas l'espace du tableau d'entrée.

Pour résumer, le tri rapide est un algorithme de tri efficace avec une faible complexité temporelle et spatiale. Dans les applications pratiques, bien que la complexité temporelle du tri rapide dans le pire des cas soit O(n^2), la complexité temporelle du tri rapide dans le cas moyen est O(nlogn), et les données dans les applications pratiques sont très petites. -le scénario est moins probable, donc le tri rapide est toujours un algorithme de tri par sélection.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!