PHP 函数的 Big-O 列表

因为在我认为将它放在某个地方供参考之前似乎没有人这样做过。我已经通过基准测试或代码略读来描述 array_* 函数。我试图将更有趣的 Big-O 放在顶部附近。此列表不完整。

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

有趣的点：

isset/array_key_exists 比 in_array 快得多，并且 array_search +(union) 比 array_merge 快一点（看起来更好）。但它的工作方式确实不同，所以请记住这一点。 shuffle 与 array_rand 在同一 Big-O 层上 array_pop/array_push 由于重新索引惩罚而比 array_shift/array_unshift 快

查找：

array_key_exists 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, 对于所有 i)

array_pop O(1)

array_shift O(n) - 它必须重新索引所有键

array_unshift O(n + ∑ var_i, for all i) - 它必须重新索引所有键

数组交集、并集、减法：

array_intersect_key 如果相交 100% 做 O(Max(param_i_size)*∑param_i_count, for all i), if相交 0% intersect O(∑param_i_size, for all i)

array_intersect 如果相交 100% 做 O(n^2*∑param_i_count, 对于所有 i)，如果相交 0% 相交 O(n^2)

array_intersect_assoc 如果相交 100% 做 O(Max(param_i_size)*∑param_i_count, for all i), if相交 0% intersect O(∑param_i_size, for all i)

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

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, 对于所有 i )

随机的：

shuffle O(n)

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

明显的大O：

array_fill O(n)

array_fill_keys O(n)

range O(n)

array_splice O(偏移 + 长度)

array_slice O(offset + length) 或 O(n) 如果长度 = NULL

array_keys O(n)

array_values O(n)

array_reverse O(n)

array_pad O(pad_size)

array_flip O(n)

array_sum O(n)

array_product O(n)

array_reduce O(n)

array_filter O(n)

array_map O(n)

array_chunk O(n)

array_combine O(n)

我要感谢 Eureqa 使查找函数的 Big-O 变得容易。这是一个了不起的免费程序，可以找到任意数据的最佳拟合函数。

编辑：

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

https://i.stack.imgur.com/PgRQd.png

$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 );
}

---

您具体描述的情况的解释是关联数组被实现为哈希表 - 所以按键查找（相应地，array_key_exists）是O（1）。但是，数组不是按值索引的，因此在一般情况下，发现数组中是否存在值的唯一方法是线性搜索。那里没有惊喜。

我认为没有关于 PHP 方法算法复杂性的具体综合文档。但是，如果这是一个足够大的问题，值得付出努力，您可以随时查看 the source code。

---

您几乎总是希望使用 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 秒

当然，这并没有显示时间复杂度，但它确实显示了 2 个函数如何相互比较。

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

---

如果人们在实践中遇到关键冲突问题，他们会使用辅助哈希查找或平衡树来实现容器。平衡树将给出 O(log n) 最坏情况行为和 O(1) avg。大小写（哈希本身）。在内存应用程序的大多数实际应用中，开销是不值得的，但也许有些数据库将这种形式的混合策略实现为默认情况。

---