Bagaimana untuk mencari median tatasusunan yang sangat besar dalam php

Dalam PHP, kadangkala kita perlu memproses tatasusunan yang sangat besar, seperti mencari median. Tetapi untuk tatasusunan yang sangat besar, menggunakan kaedah pengisihan tradisional akan sangat memakan masa dan memakan memori. Jadi, adakah cara yang lebih cekap untuk mencari median tatasusunan yang sangat besar? Artikel ini akan memperkenalkan kaedah penyelesaian yang cekap berdasarkan algoritma pemilihan pantas.

1. Pengenalan kepada algoritma pemilihan pantas

Algoritma pemilihan pantas ialah algoritma yang dipertingkatkan berdasarkan algoritma isihan pantas. Idea utamanya ialah mencari item dalam tatasusunan tidak tertib melalui pembahagian pantas Unsur terkecil k. Kerumitan masanya ialah O(n), yang lebih cekap daripada kerumitan masa algoritma pengisihan konvensional O(n log n).

Langkah asas algoritma pemilihan pantas adalah seperti berikut:

1. Pilih pangsi elemen pangsi (biasanya elemen pertama dalam tatasusunan); elemen pangsi dalam tatasusunan Elemen dibahagikan kepada dua bahagian: lebih kecil daripada pangsi dan lebih besar daripada pangsi
2. Jika bilangan elemen yang lebih kecil daripada pangsi adalah kurang daripada k, teruskan mencari elemen ke-k antara; elemen lebih besar daripada pivot;
3. Jika kurang daripada Jika bilangan elemen pivot lebih besar daripada atau sama dengan k, maka teruskan mencari elemen ke-k di antara elemen yang lebih kecil daripada pivot; > Ulang langkah di atas sehingga unsur ke-k ditemui.
4. Cari median tatasusunan yang sangat besar
5. Kami kini mempertimbangkan cara menggunakan algoritma pemilihan pantas untuk mencari median tatasusunan yang sangat besar. Katakan kita mempunyai tatasusunan yang sangat besar $nums$ dan perlu mencari mediannya. Mula-mula kami melakukan pembahagian pantas pada $nums$, membahagikan elemen kepada dua bahagian yang lebih kecil daripada pivot dan lebih besar daripada pivot. Jika pangsi betul-betul di tengah tatasusunan, maka ia adalah median. Jika tidak, berdasarkan lokasi pangsi, kita boleh menilai bahawa carian harus diteruskan di sebelah tempat pangsi itu berada.
6. Berikut ialah langkah algoritma terperinci:

Pertama, kita perlu menentukan kedudukan pertengahan median. Jika bilangan elemen $n$ dalam tatasusunan ialah nombor ganjil, median ialah $nums[(n-1)/2]$ jika bilangan elemen $n$ ialah nombor genap, median ialah $(; angka[n /2-1]+bilangan[n/2])/2$.

Cepat bahagikan tatasusunan $nums$ dan rekod kedudukan pangsi $pos$.

1. Berdasarkan hubungan kedudukan antara pos dan pertengahan, tentukan sama ada median berada di sebelah kiri atau kanan pangsi. Jika $pos< pertengahan$, maka median adalah antara kedudukan $[pos+1,n-1]$; jika $pos>=mid$, maka median adalah antara kedudukan $[0,pos-1]$ antara.
2. Ulang langkah 2 dan 3 sehingga median ditemui.
3. Berikut ialah pelaksanaan kod PHP yang sepadan:

Ringkasan

function quickSelect($nums, $k) {
    $n = count($nums);
    $left = 0;
    $right = $n - 1;
    $mid = ($n - 1) / 2;

    while (true) {
        $pos = partition($nums, $left, $right);
        if ($pos == $mid) {
            if ($n % 2 == 0) {
                // 偶数个元素
                return ($nums[$pos] + $nums[$pos + 1]) / 2;
            } else {
                // 奇数个元素
                return $nums[$pos];
            }
        } elseif ($pos < $mid) {
            $left = $pos + 1;
        } else {
            $right = $pos - 1;
        }
    }
}

function partition(&$nums, $left, $right) {
    $pivot = $nums[$left];
    $i = $left;
    $j = $right;

    while ($i < $j) {
        while ($i < $j && $nums[$j] >= $pivot) {
            $j--;
        }
        while ($i < $j && $nums[$i] <= $pivot) {
            $i++;
        }
        if ($i < $j) {
            $temp = $nums[$i];
            $nums[$i] = $nums[$j];
            $nums[$j] = $temp;
        }
    }

    // 将pivot元素放到正确的位置
    $nums[$left] = $nums[$i];
    $nums[$i] = $pivot;

    return $i;
}

// 测试示例
$nums = array(1, 2, 3, 4, 5, 6, 7, 8, 9);
echo quickSelect($nums, 5); // 输出5（因为5在数组中的中间位置）

Untuk tatasusunan yang sangat besar, menggunakan kaedah pengisihan tradisional akan membawa Datang dengan kerumitan masa dan ruang yang sangat tinggi. Dengan menggunakan algoritma pemilihan pantas untuk mencari elemen terkecil ke-k, kita boleh melengkapkan operasi dalam kerumitan masa O(n), dengan itu mencapai penyelesaian yang cekap kepada median tatasusunan yang sangat besar. Perlu diingatkan bahawa dalam penggunaan sebenar, kita juga perlu melakukan pengoptimuman yang sesuai mengikut keperluan yang berbeza, seperti pemangkasan, dll.

Atas ialah kandungan terperinci Bagaimana untuk mencari median tatasusunan yang sangat besar dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!