PHP 배열의 특정 요소를 검색하는 알고리즘 효율성 비교

PHP 배열 요소 검색 알고리즘 효율성 비교: 선형 검색: 순서가 지정되지 않은 배열의 효율성은 O(n)입니다. (순서 있는 배열): 시간 복잡도는 O(log n)입니다. 시간 복잡도는 항상 O(1)입니다. , 배열 유형에 관계없이.

PHP 배열에서 특정 요소를 찾는 알고리즘 효율성 비교

배열에서 특정 요소를 찾는 것은 PHP의 일반적인 작업이며 이 목적에 사용할 수 있는 다양한 알고리즘이 있습니다. 이 기사에서는 가장 일반적인 세 ​​가지 알고리즘의 효율성을 비교합니다.

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

실용 사례

우리는 테스트를 위해 서로 다른 크기의 배열, 순서가 없는 배열, 무작위 요소를 포함하는 순서 배열을 사용했습니다. 결과는 다음과 같습니다.

Algorithm

Unordered arrayOrdered arrayO(n)O(n)O(log n)O(1)이진 검색은 순서 배열, 시간 복잡도에서 가장 잘 수행됩니다. O(log n)이고 해시 테이블은 모든 경우에 가장 효율적이며 시간 복잡도는 항상 O(1)입니다.

		Linear search
	B 단일 검색	O( log n)
	해시 테이블	O(1)
		Conclusion

위 내용은 PHP 배열의 특정 요소를 검색하는 알고리즘 효율성 비교의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!