Ketahui prinsip dan analisis kerumitan masa bagi mengira algoritma pengisihan dalam PHP.

Ketahui prinsip dan analisis kerumitan masa algoritma pengisihan mengira dalam PHP

Isihan mengira ialah algoritma pengisihan bukan perbandingan, sesuai untuk situasi di mana julat data kecil dan diketahui. Idea asasnya ialah mengira bilangan kejadian setiap elemen dan kemudian mengisinya ke dalam tatasusunan keluaran untuk mencapai pengisihan. Artikel ini akan memperkenalkan prinsip, langkah dan analisis kerumitan masa pengisihan mengira, dan menyediakan contoh kod PHP khusus.

1. Prinsip:
   Prinsip pengisihan mengira agak mudah. Andaikan tatasusunan yang hendak diisih ialah tatasusunan, dan julat elemen ialah [0, k]. Semasa mengulangi tatasusunan asal, unsur-unsur dikira dan disimpan dalam tatasusunan kiraan. Kemudian, kami secara berurutan mengumpul elemen dalam tatasusunan kiraan untuk menentukan kedudukan elemen dalam tatasusunan keluaran. Akhir sekali, rentasi tatasusunan asal dan letakkan setiap elemen ke kedudukan yang sepadan (mengikut indeks dalam kiraan) untuk melengkapkan pengisihan.
2. Langkah:
3. Buat kiraan tatasusunan kiraan bersaiz k+1 dan mulakannya kepada 0.
4. Lintas tatasusunan asal, kira bilangan kejadian setiap elemen dan simpannya dalam tatasusunan kiraan.
5. Kumpul tatasusunan kiraan untuk menentukan kedudukan setiap elemen dalam tatasusunan keluaran.
6. Buat output tatasusunan output dengan saiz yang sama seperti tatasusunan asal.
7. Lintas tatasusunan asal sekali lagi dan letakkan setiap elemen ke dalam tatasusunan output mengikut indeks dalam tatasusunan kiraan.
8. Output tatasusunan output ialah hasil selepas pengisihan mengira.
9. Analisis kerumitan masa:
10. Kerumitan masa untuk mencipta tatasusunan kiraan ialah O(k).
11. Kerumitan masa merentasi tatasusunan asal dan mengira kejadian setiap elemen ialah O(n).
12. Kerumitan masa untuk mengumpul tatasusunan kiraan ialah O(k).
13. Kerumitan masa untuk mencipta tatasusunan output ialah O(n).
14. Kerumitan masa merentasi tatasusunan asal semula dan meletakkan elemen ke dalam tatasusunan output ialah O(n).
15. Jumlah kerumitan masa ialah O(k) + O(n) + O(k) + O(n) + O(n), yang dipermudahkan kepada O(n + k).

Berikut ialah contoh kod menggunakan bahasa PHP untuk melaksanakan algoritma pengisihan mengira:

function countingSort($array)
{
    $maxValue = max($array);
    $count = array_fill(0, $maxValue + 1, 0);
    $n = count($array);

    foreach ($array as $value) {
        $count[$value]++;
    }

    for ($i = 1; $i <= $maxValue; $i++) {
        $count[$i] += $count[$i - 1];
    }

    $output = array_fill(0, $n, 0);

    for ($i = $n - 1; $i >= 0; $i--) {
        $output[$count[$array[$i]] - 1] = $array[$i];
        $count[$array[$i]]--;
    }

    return $output;
}

$array = [4, 2, 0, 1, 3, 2, 1]; // 待排序数组
$sortedArray = countingSort($array);
print_r($sortedArray);

Di atas ialah kandungan mempelajari prinsip dan analisis kerumitan masa bagi algoritma pengisihan mengira dalam PHP. Saya harap ini membantu anda memahami pengisihan mengira.

Atas ialah kandungan terperinci Ketahui prinsip dan analisis kerumitan masa bagi mengira algoritma pengisihan dalam PHP.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!