Comparaison de l'efficacité des algorithmes pour rechercher des éléments spécifiques dans des tableaux PHP

Comparaison de l'efficacité de l'algorithme de recherche d'éléments de tableau PHP : recherche linéaire : l'efficacité dans un tableau non ordonné est O(n) ; recherche binaire (tableau ordonné) : la complexité temporelle est O(log n) : la complexité temporelle est toujours O (1) ; , quel que soit le type de tableau.

Comparaison de l'efficacité des algorithmes pour trouver des éléments spécifiques dans des tableaux PHP

La recherche d'éléments spécifiques dans un tableau est une tâche courante en PHP et il existe différents algorithmes disponibles à cet effet. Cet article comparera l'efficacité des trois algorithmes les plus courants :

1. Recherche linéaire

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

  return -1;
}

2. Recherche binaire (le tableau doit être ordonné)

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

3. en utilisant des paires clé-valeur pour stocker les données, les recherches peuvent être beaucoup plus rapides.

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

Cas pratique

Nous avons utilisé différentes tailles de tableaux pour les tests, des tableaux non ordonnés et des tableaux ordonnés contenant des éléments aléatoires. Les résultats sont les suivants :

La recherche binaire fonctionne mieux dans les tableaux ordonnés et a un temps complexe. Le degré est O (log n), tandis que les tables de hachage sont les plus efficaces dans tous les cas et que la complexité temporelle est toujours O (1).

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!