PHP 配列内の特定の要素を検索するアルゴリズムの効率の比較-PHPチュートリアル-php.cn

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

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

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