PHP 配列内の特定の要素を検索するアルゴリズムの効率の比較

PHP 配列要素検索アルゴリズムの効率比較: 線形検索: 順序なし配列の効率は O(n)、二分探索 (順序付き配列): 時間計算量は O(log n)、時間計算量は常に O( 1) 配列の種類に関係なく。

PHP 配列内の特定の要素を検索するアルゴリズムの効率の比較

配列内の特定の要素を検索することは、PHP の一般的なタスクです。この目的のために利用できるアルゴリズムがいくつかあります。この記事では、最も一般的な 3 つのアルゴリズムの効率を比較します:

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(1)#結論

順序なし配列	順序付き配列
		##二分検索
O(log n)		ハッシュ テーブル
O(1)

バイナリ検索は、時間計算量が O(log n) の順序付けられた配列で最高のパフォーマンスを発揮しますが、ハッシュ テーブルは順序付けされた配列で最高のパフォーマンスを発揮します。すべての場合において最も効率的であり、時間計算量は常に O(1) です。

以上がPHP 配列内の特定の要素を検索するアルゴリズムの効率の比較の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。