您的代码很
O(n^2)复杂-因此在大型数据集上效率很低。这是
O(n^2)因为您要遍历
foreach函数内部的所有数组，并
while在外部循环中调用它。
但是您可以轻松地通过以下方式完成这些工作
O(n x log(N))：
function binSearch($array, $value, $from=null, $till=null){ $from = isset($from)?$from:0; $till = isset($till)?$till:count($array)-1; if($till<$from) { return null; } $middle = (int)($from + ($till - $from)/2); if($array[$middle]>$value) { return binSearch($array, $value, $from, $middle-1); } if($array[$middle]<$value) { return binSearch($array, $value, $middle+1, $till); } return $middle;}$data = [1, 5, 3, 4, 2];$k = 2;sort($data); //O(n x log(n))$count = 0;foreach($data as $value) //O(n){ $count += null===binSearch($data, $value+$k)?0:1;//O(log(N))}var_dump($count);-so，您将使用
sort()具有
O(n log(n))复杂性的standard ，然后使用二进制搜索
N时间。二进制搜索有
O(log(n)) complexity，因此循环的复杂性也会很大
O(n log (n))。因此，整个代码的复杂度将为
O(n log(n)) + O(n log(n)) = O(n log(n))。
注意： 标准PHP
in_array()具有
O(N)复杂度，因此使用它会
O(N^2)为循环产生复杂度估计，因此会产生
O(N^2)代码复杂度。
注意： 通过排序
sort()将产生快速排序。该算法具有
O(nlog(n))平均
复杂度，最坏的情况是
O(N^2)-因此，在某些情况下可能存在数据集的情况，因此上述代码也可能效率不高。您可能会研究其他排序算法。例如，如果您的问题是时间限制，则可以尝试合并排序
-这将非常快（但是会占用更多空间）。
注意 ：如果我们谈论的是时间复杂度和空间复杂度无关紧要，则可以使用简单的哈希映射。在PHP中，它只是数组：
$array = [1, 5, 3, 4, 2];$k = 2;$count = 0;$map = [];foreach ($array as $number) //O(n) time{ $map[$number] = $number;}foreach($map as $key=>$nevermind) //O(n) time{ //O(1) if there are no duplicates, very close to O(1) otherwise $count += array_key_exists($key+$k, $map); }var_dump($count);-这将导致
O(n)时间复杂度和
O(2n)=O(n)空间复杂度。
