Vergleich der Algorithmuseffizienz für die Suche nach bestimmten Elementen in PHP-Arrays

PHP-Array-Element-Suchalgorithmus-Effizienzvergleich: lineare Suche: die Effizienz im ungeordneten Array ist O(n); binäre Suche (geordnetes Array): Zeitkomplexität ist O(log n); , unabhängig vom Array-Typ.

Vergleich der Algorithmuseffizienz zum Finden spezifischer Elemente in PHP-Arrays

Das Finden spezifischer Elemente in einem Array ist eine häufige Aufgabe in PHP und für diesen Zweck stehen verschiedene Algorithmen zur Verfügung. In diesem Artikel wird die Effizienz der drei häufigsten Algorithmen verglichen:

Lineare Suche

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

  return -1;
}

2. Binäre Suche (Array muss geordnet sein)

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;
}

Hash-Tabelle Nach Durch die Verwendung von Schlüssel-Wert-Paaren zum Speichern von Daten können Suchvorgänge erheblich schneller erfolgen.

function hashTableSearch($arr, $target) {
  $lookupTable = [];

  for ($i = 0; $i < count($arr); $i++) {
    $lookupTable[$arr[$i]] = true;
  }

  if (isset($lookupTable[$target])) {
    return true;
  } else {
    return false;
  }
}

Praktischer Fall

Wir haben verschiedene Array-Größen zum Testen verwendet, ungeordnete Arrays und geordnete Arrays mit zufälligen Elementen. Die Ergebnisse sind wie folgt:

AlgorithmusUngeordnetes ArrayGeordnetes ArrayLinear. SucheO(n)O(n) Binäre SucheO( log n)O(log n)Hash-TabelleO(1)O(1)Fazit

Die binäre Suche funktioniert am besten in geordneten Arrays und hat eine komplexe Zeit Der Grad ist O(log n), während Hash-Tabellen in allen Fällen am effizientesten sind und die Zeitkomplexität immer O(1) ist.

Das obige ist der detaillierte Inhalt vonVergleich der Algorithmuseffizienz für die Suche nach bestimmten Elementen in PHP-Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!