如果人们在实践中遇到键冲突的麻烦，他们会实现带有二级哈希查找或平衡树的容器。平衡树会给出O(log n)最坏情况和O(1)平均情况(哈希本身)。在大多数实际的内存应用程序中，这种开销并不值得，但也许有些数据库将这种形式的混合策略实现为默认情况。

如果人们在实践中遇到键冲突的麻烦，他们会实现带有二级哈希查找或平衡树的容器。平衡树会给出O(log n)最坏情况和O(1)平均情况(哈希本身)。在大多数实际的内存应用程序中，这种开销并不值得，但也许有些数据库将这种形式的混合策略实现为默认情况。

因为似乎没有人这样做之前，我认为这将是一个好主意，以供参考的地方。我已经通过基准测试或代码浏览来描述array_*函数。我试着把更有趣的Big-O放在顶部。这个列表并不完整。

注意:所有大O的计算假设哈希查找是O(1)，即使它实际上是O(n)。n的系数非常低，在查找Big-O的特性开始生效之前，存储足够大的数组的ram开销会对您造成伤害。例如，对array_key_exists的调用在N=1和N=1,000,000之间的差异是大约50%的时间增加。

有趣的点:

Isset /array_key_exists比in_array和array_search快得多 +(union)比array_merge快一点(而且看起来更好)。但它的工作方式确实不同，所以要记住这一点。 shuffle和array_rand在同一个大o层 由于重新索引的惩罚，Array_pop /array_push比array_shift/array_unshift快

查找:

array_key_存在O(n)但非常接近O(1) -这是因为碰撞中的线性轮询，但由于碰撞的几率非常小，系数也非常小。我发现您将哈希查找视为O(1)，以给出更现实的大O。例如，N=1000和N=100000之间的差异仅为50%。

isset($array[$index]) O(n)但非常接近O(1) -它使用与array_key_exists相同的查找。由于它的语言结构，如果键是硬编码的，将缓存查找，从而在重复使用相同键的情况下加快速度。

in_array O(n)——这是因为它在数组中进行线性搜索，直到找到值。

array_search O(n) -它使用与in_array相同的核心函数，但返回值。

队列功能:

array_push O(∑var_i, for all i)

最后O (1)

array_shift O(n)它需要重新索引所有的键

array_unshift O(n +∑var_i, for all i)它需要重新索引所有的键

数组交、并、减法:

如果交集100% do O(Max(param_i_size)*∑param_i_count, for all i)，如果交集0%相交O(∑param_i_size, for all i)

如果交集100% do O(n^2*∑param_i_count, for all i)，如果交集0%相交O(n^2)

array_intersect_assoc如果交集100% do O(Max(param_i_size)*∑param_i_count, for all i)，如果交集0%相交O(∑param_i_size, for all i)

array_diff O(π param_i_size, for all i) -这是所有param_size的乘积

array_diff_key O(∑param_i_size, for i != 1)——这是因为我们不需要遍历第一个数组。

array_merge O(∑array_i, i != 1) -不需要遍历第一个数组

+ (union) O(n)，其中n是第二个数组的大小(即array_first + array_second) -开销比array_merge少，因为它不需要重新编号

array_replace O(∑array_i, for all i)

随机:

shuffle O (n)

array_rand O(n) -需要线性轮询。

明显的大0:

array_fill O (n)

array_fill_keys O (n)

范围O (n)

array_splice O(offset + length)

array_slice(偏移量+长度)或O(n)如果长度= NULL

中的O (n)

元素O (n)

array_reverse O (n)

array_pad O (pad_size)

array_flip O (n)

函数的O (n)

array_product O (n)

形式O (n)

array_filter O (n)

到O (n)

array_chunk O (n)

合二为一O (n)

我要感谢Eureqa使查找大o函数变得很容易。这是一个神奇的免费程序，可以为任意数据找到最佳拟合函数。

编辑:

对于那些怀疑PHP数组查找是O(N)的人，我已经编写了一个基准测试(对于大多数实际值，它们仍然有效地是O(1))。

$tests = 1000000;
$max = 5000001;


for( $i = 1; $i <= $max; $i += 10000 ) {
    //create lookup array
    $array = array_fill( 0, $i, NULL );

    //build test indexes
    $test_indexes = array();
    for( $j = 0; $j < $tests; $j++ ) {
        $test_indexes[] = rand( 0, $i-1 );
    }

    //benchmark array lookups
    $start = microtime( TRUE );
    foreach( $test_indexes as $test_index ) {
        $value = $array[ $test_index ];
        unset( $value );
    }
    $stop = microtime( TRUE );
    unset( $array, $test_indexes, $test_index );

    printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
    unset( $stop, $start );
}

你总是想使用isset而不是array_key_exists。我没有查看内部内容，但我非常确定array_key_exists是O(N)，因为它遍历数组的每个键，而isset尝试使用访问数组索引时使用的相同哈希算法访问元素。应该是O(1)

需要注意的一个“陷阱”是:

$search_array = array('first' => null, 'second' => 4);

// returns false
isset($search_array['first']);

// returns true
array_key_exists('first', $search_array);

---

我很好奇，所以我对差异进行了基准测试:

<?php

$bigArray = range(1,100000);

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    isset($bigArray[50000]);
}

echo 'is_set:', microtime(true) - $start, ' seconds', '<br>';

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    array_key_exists(50000, $bigArray);
}

echo 'array_key_exists:', microtime(true) - $start, ' seconds';
?>

Is_set: 0.132308959961秒 Array_key_exists: 2.33202195168秒

当然，这并没有显示时间复杂度，但它确实显示了两个函数之间的比较。

要测试时间复杂度，请比较在第一个键和最后一个键上运行其中一个函数所花费的时间。

对于您具体描述的情况的解释是，关联数组被实现为哈希表—因此按键查找(相应地，array_key_exists)是O(1)。但是，数组不是按值建立索引的，因此在一般情况下，发现数组中是否存在值的唯一方法是线性搜索。这没什么好惊讶的。

我不认为有关于PHP方法的算法复杂性的具体全面的文档。但是，如果问题大到值得考虑，您总是可以查看源代码。