欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

PHP二分法查找之递归和迭代详解

程序员文章站 2022-05-12 08:32:45
...
关于递归和迭代分别的时间复杂度,递归的时间复杂度是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;

相关推荐:

二分法查找介绍及实例详解

JavaScript如何使用二分法查找数据的方法介绍

二分法查找数组中的元素

以上就是PHP二分法查找之递归和迭代详解的详细内容,更多请关注其它相关文章!

相关标签: php 详解 迭代