用于PHP函数的Big-O列表
现在使用PHP一段时间后，我注意到并不是所有的PHP函数的function都像预期的那样快。 考虑以下两种可能的函数实现，使用caching的素数arrays来查找数字是否为素数。
//very slow for large $prime_array $prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... ); $result_array = array(); foreach( $prime_array => $number ) { $result_array[$number] = in_array( $number, $large_prime_array ); } //speed is much less dependent on size of $prime_array, and runs much faster. $prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL, 11 => NULL, 13 => NULL, .... 104729 => NULL, ... ); foreach( $prime_array => $number ) { $result_array[$number] = array_key_exists( $number, $large_prime_array ); } 这是因为in_array是通过一个线性searchO（n）实现的，这个线性search会随着$prime_array增长而线性减速。 其中array_key_exists函数是用散列查找O（1）来实现的，除非散列表得到极度填充（在这种情况下它只有O（n）），否则它将不会变慢。
到目前为止，我不得不通过反复试验来发现big-O，偶尔还要看源代码 。 现在对于这个问题
是否有一个理论（或实际）的大O时代的所有PHP内置函数列表？
*或至less是有趣的
例如，很难预测列出的函数的大O，因为可能的实现依赖于PHP的未知核心数据结构：array_merge，array_merge_recursive，array_reverse，array_intersect，array_combine，str_replace（带数组input）等等。
由于它似乎并没有任何人以前做过，所以我认为这是一个好主意，以供参考的地方。 我已经去了，无论是通过基准testing或代码撇取来表征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 -
+（联合）比array_merge快一点（看起来更好）。 但它的工作方式不同，所以记住这一点。 -
shuffle与array_rand在同一个Big-O层上 - 由于重新索引惩罚，
array_pop/array_push比array_shift/array_unshift快
查找 ：
array_key_exists O（n）但是非常接近于O（1） – 这是因为碰撞中的线性轮询，但是由于碰撞的几率很小，系数也很小。 我发现你把HASH查找当作O（1）来给出一个更现实的big-O。 例如，N = 1000和N = 100000之间的差异只有大约50％的减速。
isset( $array[$index] ) O（n）但真正接近O（1） – 它使用与array_key_exists相同的查找。 由于它是语言结构，如果密钥是硬编码的，它将caching查找，从而在重复使用相同密钥的情况下导致加速。
in_array O（n） – 这是因为它通过数组进行线性search直到find值。
array_search O（n） – 它使用与in_array相同的核心函数，但返回值。
队列function ：
array_push O（Σvar_i，对于所有我）
array_pop O（1）
array_shift O（n） – 它必须重新索引所有的键
array_unshift O（n +Σvar_i，对于所有我） – 它必须重新索引所有的键
arrays相交，联合，减法 ：
array_intersect_key如果相交100％做O（Max（param_i_size）*Σparam_i_count，对于所有我），如果相交0％相交O（Σparam_i_size，对于所有我）
array_intersect如果相交100％做O（n ^ 2 *Σparam_i_count，对于所有我），如果相交0％相交O（n ^ 2）
array_intersect_assoc如果相交100％做O（Max（param_i_size）*Σparam_i_count，对于所有我），如果相交0％相交O（Σparam_i_size，对于所有我）
array_diff O（πparam_i_size，对于所有我） – 这是所有param_sizes的产物
array_diff_key O（Σparam_i_size，对于i！= 1） – 这是因为我们不需要迭代第一个数组。
array_merge O（Σarray_i，i！= 1） – 不需要迭代第一个数组
+ （union）O（n），其中n是第二个数组的大小（即array_first + array_second） – 比array_mergeless开销，因为它不必重新编号
array_replace O（Σarray_i，对于所有我）
随机 ：
shuffle O（n）
array_rand O（n） – 需要线性轮询。
明显的大O ：
array_fill O（n）
array_fill_keys O（n）
range O（n）
array_splice O（offset + length）
array_slice O（offset + length）或者O（n）如果length = 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让我们很容易地findfunction的大O. 这是一个惊人的免费程序，可以find任意数据的最佳拟合function。
编辑：
对于那些怀疑PHP数组查询是O(N) ，我写了一个基准testing（对于大多数实际值，它们仍然是有效的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尝试使用相同的哈希algorithm来访问该元素你访问一个数组索引。 那应该是O（1）。
一个“窍门”要注意的是：
$search_array = array('first' => null, 'second' => 4); // returns false isset($search_array['first']); // returns true array_key_exists('first', $search_array);
我很好奇，所以我testing了这个区别：
<?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秒
当然，这并不显示时间复杂性，但它确实显示了这两个函数是如何相互比较的。
要testing时间复杂性，请比较在第一个键和最后一个键上运行这些function所需的时间。
你特别描述的情况的解释是关联数组被实现为散列表 – 所以通过键（和相应的array_key_exists ）查找是O（1）。 但是，数组并不是按值进行索引的，因此在一般情况下发现数组中是否存在值的唯一方法是线性search。 那里并不奇怪。
我不认为有PHP方法的algorithm复杂性的具体全面的文档。 但是，如果需要付出很大的努力，您可以随时查看源代码 。
