이번에는 PHP 순서 테이블 검색 및 보간 검색 알고리즘의 단계에 대해 자세히 설명하겠습니다. PHP 순서 테이블 검색 및 보간 검색 알고리즘의 주의 사항은 무엇입니까?
서문:
앞서 이진 검색을 소개했는데, 생각해보면 왜 반으로 접어야 할까요? 4분의 1 이상으로 접는 것보다?
예를 들어 영어 사전에서 "사과"를 검색할 때 사전을 펼칠 때 무의식적으로 앞 페이지로 넘어가나요, 아니면 뒷 페이지로 넘어가나요? "동물원"을 다시 확인하면 어떻게 확인하나요? 당연히 사전의 중간부터 찾아보기 시작하는 것이 아니라, 어떤 목적을 가지고 앞이나 뒤를 바라봅니다.
마찬가지로, 예를 들어 0 ~ 10000 범위에서 작은 것부터 큰 것까지 균등하게 분포된 100개의 요소가 있는 배열에서 5를 찾으려면 자연스럽게 더 작은 배열 첨자를 먼저 고려하여 검색을 시작합니다.
위 분석은 실제로 이진 검색을 개선한 보간 검색 아이디어입니다.
기본 아이디어:
검색 방법은 검색할 키워드 키를 조회 테이블의 최대 및 최소 레코드의 키워드와 비교하는 것입니다. 그 핵심은 보간 계산 공식에 있습니다. 먼저 반탐색 계산식을 살펴보세요:
보간탐색은 1/2을 개선하여 다음 계산계획으로 변경합니다.
보간탐색 알고리즘의 핵심은 보간 계산 공식:
$num - $arr[$lower]
——————————————
$arr[$high] - $arr[$lower]
코드:
<?php //插值查找(前提是数组必须是有序数组) 事件复杂度 O(logn) //但对于数组长度比较大,关键字分布又是比较均匀的来说,插值查找的效率比折半查找的效率高 $i = 0; //存储对比的次数 //@param 待查找数组 //@param 待搜索的数字 function insertsearch($arr,$num){ $count = count($arr); $lower = 0; $high = $count - 1; global $i; while($lower <= $high){ $i ++; //计数器 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;
요약:
시간 복잡도 관점에서 보면 O(logn)이지만 순서가 긴 목록과 상대적으로 고르게 분포된 조회 테이블의 경우 키워드, 보간 조회 알고리즘의 평균 성능은 좋은 키워드를 많이 찾기보다 두 배 높습니다. 반대로 배열 내 분포가 {0, 1, 2, 2000, 2001,. . . 999998, 999999} 보간 검색을 사용하는 이러한 종류의 매우 고르지 않은 데이터는 그다지 적합한 선택이 아닐 수 있습니다.
직접 예제를 만들었습니다:
$arr = array(0,1,2,2000,2001,2002,2003,2004,5555,69666,99999,100000); echo "位置:".binsearch($arr,5555); echo "<br>"; echo "比较次数:".$i; $i = 0; //重置比较次数 echo "<br>"; echo "位置:".insertsearch($arr,5555); echo "<br>"; echo "比较次数:".$i;
결과 출력:
位置:8 比较次数:2 位置:8 比较次数:9
매우 고르지 않은 데이터의 경우 보간 검색 효율성이 절반 검색보다 낮다는 것을 알 수 있습니다.
PS 기타 관련 기사가 온라인에 있습니다! PHP 긴 연결 사용 사례 분석위 내용은 PHP 순서 목록 검색 보간 검색 알고리즘의 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!