Perbandingan kecekapan algoritma untuk mencari elemen tertentu dalam tatasusunan PHP

Perbandingan kecekapan algoritma carian elemen tatasusunan PHP: carian linear: kecekapan dalam tatasusunan tidak tertib ialah O(n); ), tanpa mengira jenis tatasusunan.

Perbandingan Kecekapan Algoritma untuk Mencari Elemen Khusus dalam Tatasusunan PHP

Mencari elemen khusus dalam tatasusunan ialah tugas biasa dalam PHP dan terdapat pelbagai algoritma yang tersedia untuk tujuan ini. Artikel ini akan membandingkan kecekapan tiga algoritma yang paling biasa:

1. Carian linear

function linearSearch($arr, $target) {
  for ($i = 0; $i < count($arr); $i++) {
    if ($arr[$i] === $target) {
      return $i;
    }
  }

  return -1;
}

2 menggunakan pasangan nilai kunci untuk menyimpan data, carian boleh menjadi lebih pantas dengan ketara.

function binarySearch($arr, $target) {
  $left = 0;
  $right = count($arr) - 1;

  while ($left <= $right) {
    $mid = floor(($left + $right) / 2);

    if ($arr[$mid] === $target) {
      return $mid;
    } else if ($arr[$mid] < $target) {
      $left = $mid + 1;
    } else {
      $right = $mid - 1;
    }
  }

  return -1;
}

Kes praktikal

Kami menggunakan saiz tatasusunan yang berbeza untuk ujian, tatasusunan tidak tersusun dan tatasusunan tersusun yang mengandungi unsur rawak. Keputusannya adalah seperti berikut:

Algoritma

Tatasusunan tidak tertib

Tatasusunan tertibCarian linearO(n)O(n)Carian binarijadual cincang prestasi carian tersusun terbaik dan masa yang kompleks darjah ialah O(log n), manakala jadual cincang adalah yang paling cekap dalam semua kes, dan kerumitan masa sentiasa O(1).

O( log n)	O(log n)
O(1)	O(1)
Kesimpulan

Atas ialah kandungan terperinci Perbandingan kecekapan algoritma untuk mencari elemen tertentu dalam tatasusunan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!