欧美成人午夜免费全部完,亚洲午夜福利精品久久,а√最新版在线天堂,另类亚洲综合区图片小说区,亚洲欧美日韩精品色xxx

扣丁學(xué)堂PHP視頻教程之PHP有序表查找之插值查找算法

2018-07-18 17:14:55 1102瀏覽

關(guān)于PHP開發(fā)技術(shù)相信大家對(duì)此并不陌生，因?yàn)槿缃窀鞔蠊酒髽I(yè)都會(huì)有專門的PHP開發(fā)工程師在工作，本篇文章扣丁學(xué)堂PHP培訓(xùn)小編主要是給喜歡PHP的小伙伴們分享一個(gè)PHP有序表查找之插值查找算法示例，感興趣的小伙伴隨著小編一起來(lái)了解一下吧。

本文實(shí)例講述了PHP有序表查找之插值查找算法。分享給大家供大家參考，具體如下：

基本思想：

根據(jù)要查找的關(guān)鍵字key與查找表中的最大最小記錄的關(guān)鍵字比較后的查找方法，其核心就在于插值計(jì)算公式，我們先看折半查找的計(jì)算公式：

而插值查找就是要將其中的 1/2進(jìn)行改進(jìn)，改成下面的計(jì)算方案：

插值查找算法的核心就在于插值的計(jì)算公式:

$num - $arr[$lower] 
————————————— 
$arr[$high] - $arr[$lower]

代碼：

<?php
//插值查找(前提是數(shù)組必須是有序數(shù)組) 事件復(fù)雜度　O(logn)
//但對(duì)于數(shù)組長(zhǎng)度比較大，關(guān)鍵字分布又是比較均勻的來(lái)說(shuō)，插值查找的效率比折半查找的效率高
$i = 0; //存儲(chǔ)對(duì)比的次數(shù)
//@param 待查找數(shù)組
//@param 待搜索的數(shù)字
function insertsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //計(jì)數(shù)器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  // 折半查找 ： $middle = intval(($lower + $high) / 2);
  $middle = intval($lower + ($num - $arr[$lower]) / ($arr[$high] - $arr[$lower]) * ($high - $lower)); 
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = insertsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

總結(jié)：

從時(shí)間復(fù)雜度上來(lái)看，它也是 O(logn)，但對(duì)于有序表比較長(zhǎng)，而關(guān)鍵字分布有比較均勻的查找表來(lái)說(shuō)，插值查找算法的平均性能比二分查找好的多。反之，數(shù)組中如果分布類似于{0，1，2，2000，2001，。。。999998，999999}這種極端不均勻的數(shù)據(jù)，用插值查找未必是很合適的選擇。

以上就是扣丁學(xué)堂PHP培訓(xùn)小編給大家分享的PHP有序表查找之插值查找算法示例，希望對(duì)小伙伴們有所幫助，想要了解更多關(guān)于PHP開發(fā)方面內(nèi)容的小伙伴可以登錄扣丁學(xué)堂官網(wǎng)咨詢?？鄱W(xué)堂不僅有專業(yè)的PHP培訓(xùn)班供大家學(xué)習(xí)，還有與時(shí)俱進(jìn)的課程體系和大量的PHP在線視頻教程讓學(xué)員免費(fèi)觀看學(xué)習(xí)，想要學(xué)好PHP的小伙伴快到扣丁學(xué)堂來(lái)了解詳情吧?？鄱W(xué)堂PHP技術(shù)交流群：374332265。

【關(guān)注微信公眾號(hào)獲取更多學(xué)習(xí)資料】

查看更多關(guān)于“php培訓(xùn)資訊”的相關(guān)文章>>