2024-05-01

PHP数组特定元素查找的算法效率比较

php 数组元素查找算法效率比较:线性搜索:无序数组中效率为 o(n);二分搜索(有序数组):时间复杂度为 o(log n);散列表:时间复杂度始终为 o(1),无论数组类型。

PHP数组特定元素查找的算法效率比较

PHP 数组特定元素查找的算法效率比较

在 PHP 中查找数组中的特定元素是常见的任务,有多种算法可用于此目的。本文将比较三种最常见的算法的效率:

1. 线性搜索

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

  return -1;
}
登录后复制

2. 二分搜索(数组必须是有序的)

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. 散列表

散列表通过使用键值对来存储数据,可以显著提高查找速度。

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;
  }
}
登录后复制

实战案例

我们使用不同的数组大小进行测试,包含随机元素的无序数组和有序数组。结果如下:

算法 无序数组 有序数组
线性搜索 O(n) O(n)
二分搜索 O(log n) O(log n)
散列表 O(1) O(1)

结论

二分搜索在有序数组中表现最佳,时间复杂度为 O(log n),而散列表在所有情况下效率最高,时间复杂度始终为 O(1)。

以上就是PHP数组特定元素查找的算法效率比较的详细内容,更多请关注php中文网其它相关文章!

https://www.php.cn/faq/772676.html

发表回复

Your email address will not be published. Required fields are marked *