PHP 数组 - 删除重复项(时间复杂度)

Question

好吧，这不是“如何获取所有唯一值”或“如何从我的 php 数组中删除重复项”的问题。这是一个关于时间复杂度的问题。

我认为 array_unique 有点 O(n^2 - n)，这是我的实现:

function array_unique2($array) 
{ 
    $to_return = array(); 
    $current_index = 0;

    for ( $i = 0 ; $i < count($array); $i++ ) 
    { 
        $current_is_unique = true; 

        for ( $a = $i+1; $a < count($array); $a++ ) 
        { 
            if ( $array[$i] == $array[$a] ) 
            { 
                $current_is_unique = false; 
                break; 
            } 
        } 
        if ( $current_is_unique ) 
        { 
            $to_return[$current_index] = $array[$i];
        } 

    } 

    return $to_return; 
}

然而，当针对 array_unique 进行基准测试时，我得到了以下结果:

正在测试 (array_unique2)... 操作耗时 0.52146291732788 秒。

正在测试 (array_unique)...操作耗时 0.28323101997375 秒。

这使得 array_unique 快了一倍，我的问题是，为什么(两者都有相同的随机数据)？

我的一个 friend 写道:

function array_unique2($a)
{
    $n = array();
    foreach ($a as $k=>$v)
        if (!in_array($v,$n))
            $n[$k]=$v;
    return $n;
}

比 php 中的内置速度快一倍。

我想知道，为什么？

array_unique 和 in_array 的时间复杂度是多少？

编辑我从两个循环中删除了 count($array) 并且只在函数顶部使用了一个变量，它在 100 000 个元素上获得了 2 秒!

Answer 1

虽然我不能代表原生的 array_unique 函数，但我可以告诉你你 friend 的算法更快，因为:

1. 他使用单个 foreach 循环而不是您的双 for() 循环。
2. Foreach 循环往往比 PHP 中的 for 循环执行得更快。
3. 他使用了一个 if(!) 比较，而你使用了两个 if() 结构
4. 您 friend 调用的唯一附加函数是 in_array，而您调用了 count() 两次。
5. 你做了三个你 friend 不需要的变量声明($a, $current_is_unique, $current_index)

虽然单独这些因素都不是很大，但我可以看到累积效应会使您的算法比您的 friend 花费更长的时间。