ホームページ >バックエンド開発 >PHPチュートリアル >PHP二分探索の再帰と反復について詳しく解説
再帰と反復のそれぞれの時間計算量に関して、再帰の時間計算量は O(N) ですが、反復の時間計算量は O(logN) であることが、2 つの曲線 y=N と Y=logN からわかります。 O(logN) の方が良いです。この記事では主に PHP バイナリ検索の再帰と反復について詳しく説明します。お役に立てれば幸いです。
以下は 2 つのコードと、確実な効率テスト用のコードです。
<?php function dichotomyIterationSearch($arr, $n, $v) { $left = 0; $right = $n - 1; while ($left <= $right) { $middle = bcp(bcadd($right, $left), 2); if ($arr[$middle] > $v) { $right = $middle - 1; } elseif ($arr[$middle] < $v) { $left = $middle + 1; } else { return $middle; } } return -1; } $arr = []; for ($i=0;$i<300000;$i++){ $arr[] = $i; } list($first) = explode(" ",microtime()); echo dichotomyIterationSearch($arr,count($arr),35387);echo '<br>'; list($second) = explode(" ",microtime()); echo round($second - $first,5)*1000000; function dichotomyRecursionSearch($arr, $low, $high, $v) { $middle = bcp(bcadd($low, $high), 2); if ($low < $high) { if ($arr[$middle] > $v) { $high = $middle - 1; return dichotomyRecursionSearch($arr, $low, $high, $v); } elseif ($arr[$middle] < $v) { $low = $middle + 1; return dichotomyRecursionSearch($arr, $low, $high, $v); } else { return $middle; } } elseif ($high == $low) { if ($arr[$middle] == $v) { return $middle; } else { return -1; } } return -1; } $arr = []; for ($i=0;$i<300000;$i++){ $arr[] = $i; } echo "<br>"; list($first) = explode(" ",microtime()); echo dichotomyRecursionSearch($arr,0, count($arr),35387);echo '<br>'; list($second) = explode(" ",microtime()); echo round($second - $first, 5)*1000000;
関連する推奨事項:
JavaScript が二分検索を使用してデータを検索する方法の紹介
以上がPHP二分探索の再帰と反復について詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。