关于递归和迭代分别的时间复杂度,递归的时间复杂度是O(N),而迭代的时间复杂度是O(logN),由y=N 和Y=logN两条曲线我们知道,一定是O(logN)更优一些。本文主要和大家分享PHP二分法查找之递归和迭代详解,希望能帮助到大家。
以下是两段代码,和傻瓜式测效率的代码。
<?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;
相关推荐:
以上是PHP二分法查找之递归和迭代详解的详细内容。更多信息请关注PHP中文网其他相关文章!