PHP的Big-O列表

由于似乎没有人做过此事，因此我认为最好在某个地方提供参考。我已经通过基准测试或代码掠过来表征这些array_*功能。我试图将更有趣的Big-O放在顶部。此列表不完整。

注意：假设是哈希查找，所有计算出来的Big-O都是O（1），即使它实际上是O（n）。n的系数是如此之低，在大Big-O的特征开始生效之前，存储足够大的数组的内存开销会伤害您。例如，array_key_exists在N = 1和N = 1,000,000时的通话时间差为〜50％。

有趣的地方：

isset/ array_key_exists比in_array和快得多array_search +（联盟）比array_merge（看起来更好）快一点。但是它的工作方式有所不同，因此请记住这一点。 shuffle 在与Big-O相同的层上 array_rand array_pop/ array_push比重新索引罚款更快array_shift/array_unshift 查询：

array_key_existsO（n）但实际上接近O（1）-这是由于碰撞中的线性轮询，但是由于碰撞的机会非常小，因此系数也非常小。我发现您将哈希查找视为O（1）来给出更现实的big-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，对于所有i）-必须重新索引所有键

数组相交，并集，减法：

array_intersect_key 如果交集100％进行O（Max（param_i_size）* ∑param_i_count，对于所有i），如果交集0％相交O（∑param_i_size，对于所有i）

array_intersect 如果交集100％对所有i执行O（n ^ 2 * ∑param_i_count，对于所有i），如果交集0％与O（n ^ 2）相交

array_intersect_assoc 如果交集100％进行O（Max（param_i_size）* ∑param_i_count，对于所有i），如果交集0％相交O（∑param_i_size，对于所有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）-不需要遍历第一个数组

• （联合）O（n），其中n是第二个数组的大小（即array_first + array_second）-比array_merge少的开销，因为它不必重新编号

array_replace O（∑ array_i，对于所有i）

随机：

shuffle 上）

array_rand O（n）-需要线性轮询。

明显的Big-O：

array_fill 上）

array_fill_keys 上）

range 上）

array_splice O（偏移量+长度）

array_slice O（偏移量+长度）或O（n）如果长度= NULL

array_keys 上）

array_values 上）

array_reverse 上）

array_pad O（pad_size）

array_flip 上）

array_sum 上）

array_product 上）

array_reduce 上）

array_filter 上）

array_map 上）

array_chunk 上）

array_combine 上）

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

编辑：

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

php数组查找图

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

}

问题来源于stack overflow