关于递归和迭代分别的时间复杂度,递归的时间复杂度是O(N),而迭代的时间复杂度是O(logN),由y=N 和Y=logN两条曲线我们知道,一定是O(logN)更优一些。本文主要和大家分享PHP二分法查找之递归和迭代详解,希望能帮助到大家。
以下是两段代码,和傻瓜式测效率的代码。
$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 '
'; 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 "
"; list($first) = explode(" ",microtime()); echo dichotomyRecursionSearch($arr,0, count($arr),35387);echo '
'; list($second) = explode(" ",microtime()); echo round($second - $first, 5)*1000000;
相关推荐:
위 내용은 PHP二分法查找之递归和迭代详解의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!