PHP二分法查找之遞歸與迭代詳解-php教程-PHP中文網

PHP二分法查找之遞歸與迭代詳解

小云云

發布： 2023-03-22 14:46:01

原創

1078 人瀏覽過

關於遞歸和迭代分別的時間複雜度，遞歸的時間複雜度是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;

登入後複製