由于在我认为在某个地方进行参考之前似乎没有人这样做过，因此最好将其用于参考。我已经通过基准测试或代码略读来表征函数。我试图把更有趣的Big-O放在顶部附近。此列表不完整。array_*
注意：假设哈希查找计算的所有 Big-O 都是 O（1），即使它实际上是 O（n）。n的系数非常低，在查找Big-O的特征开始生效之前，存储足够大的数组的RAM开销会伤害您。例如，在 N=1 和 N=1，000，000 时调用之间的差异约为 50% 的时间增加。array_key_exists
有趣的要点：
-
isset/array_key_exists比和快得多in_arrayarray_search
-
+（union）比（看起来更好）快一点。但它确实以不同的方式工作，所以请记住这一点。array_merge
-
shuffle与 Big-O 层相同array_rand
-
array_pop/array_push比 / 由于重新索引惩罚而快array_shiftarray_unshift
查找：
array_key_existsO（n）但非常接近O（1） - 这是因为碰撞中的线性轮询，但由于碰撞的几率非常小，系数也非常小。我发现你把哈希查找当作O（1）来给出一个更现实的大O。例如，N=1000 和 N=100000 之间的差异仅减慢约 50%。
isset( $array[$index] )O（n） 但非常接近 O（1） - 它使用与array_key_exists相同的查找。由于它是语言构造，如果密钥是硬编码的，将缓存查找，从而在重复使用相同密钥的情况下加快速度。
in_arrayO（n） - 这是因为它通过数组进行线性搜索，直到找到值。
array_searchO（n） - 它使用与in_array相同的核心函数，但返回值。
队列函数：
array_pushO（∑ var_i， for all i）
array_popO（1）
array_shiftO（n） - 它必须重新索引所有键
array_unshiftO（n + ∑ var_i，对于所有 i） - 它必须重新索引所有键
数组交集、并集、减法：
array_intersect_key如果相交 100% 做 O（最大值（param_i_size）*∑param_i_count，对于所有 i），如果相交点 0% 与 O（∑param_i_size，对于所有 i）
array_intersect如果相交 100% do O（n^2*∑param_i_count，对于所有 i），如果相交点 0% 与 O（n^2） 相交
array_intersect_assoc如果相交 100% 做 O（最大值（param_i_size）*∑param_i_count，对于所有 i），如果相交点 0% 与 O（∑param_i_size，对于所有 i）
array_diffO（π param_i_size，对于所有 i） - 这是所有param_sizes
array_diff_keyO（∑ param_i_size， for i ！= 1） - 这是因为我们不需要迭代第一个数组。
array_mergeO（ ∑ array_i， i ！= 1 ） - 不需要迭代第一个数组
+（联合）O（n），其中n是第二个数组的大小（即array_first+ array_second） - 比array_merge的开销少，因为它不必重新编号
array_replaceO（ ∑ array_i， for all i ）
随机：
shuffleO（n）
array_randO（n） - 需要线性轮询。
明显的大O：
array_fillO（n）
array_fill_keysO（n）
rangeO（n）
array_spliceO（偏移量 + 长度）
array_sliceO（偏移量 + 长度）或 O（n） 如果长度 = NULL
array_keysO（n）
array_valuesO（n）
array_reverseO（n）
array_padO（pad_size）
array_flipO（n）
array_sumO（n）
array_productO（n）
array_reduceO（n）
array_filterO（n）
array_mapO（n）
array_chunkO（n）
array_combineO（n）
我要感谢Eureqa使查找函数的Big-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 );
}
