（n）随着
in_array的增长而线性降低。 $prime_array函数是通过哈希查找O（1）实现的，除非哈希表填充得非常好（在这种情况下，它只有O（n）），否则它不会减慢速度。到目前为止，我已经我们必须通过反复试验发现big-O，偶尔查看源代码。现在要解决的问题... 是否存在所有*内置PHP函数的理论（或实践）大O时间列表？
*或在例如，我发现很难预测列出的函数的大O值，因为可能的实现取决于PHP的未知核心数据结构：
array_key_exists，array_merge，array_merge_recursive，array_reverse，array_intersect ，array_combine（带有数组输入）等。#1 楼
由于似乎没有人做过此事，因此我认为最好在某个地方提供参考。我已经通过基准测试或代码掠过来表征array_*函数。我试图将更有趣的Big-O放在顶部。该列表不完整。注意：假设哈希查找为O（1）的所有Big-O，即使它实际上是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 O（n）但实际上接近O（1）-这是由于冲突中的线性轮询，但是碰撞的机会很小，系数也很小。我发现您将哈希查找视为O（1）来给出更现实的big-O。例如，N = 1000和N = 100000之间的差异仅减慢了约50％。由于它是语言构造，因此如果密钥是硬编码的，将缓存查找，从而在重复使用同一密钥的情况下加快了查找速度。 array_shift O（n）-这是因为它对数组进行线性搜索，直到找到值为止。array_unshift O（n）-它使用相同的核用作in_array，但是返回值。队列函数：
array_key_exists O（∑ var_i，对于所有i）isset( $array[$index] ) O（1）in_array O（n）-必须重新索引所有键array_search O（n + ∑ var_i，对于所有i）-它必须重新索引所有键。如果交叉点0％相交O（对于所有i而言，O都做O（Max（param_i_size）* ∑param_i_count，对于所有i）如果交叉点100％做O（n ^ 2 * ∑param_i_count，对于所有i），如果交集0％与O（n ^ 2）相交
array_push如果交集100％进行O（Max（param_i_size）* ∑param_i_count，对于所有i），如果交集0％与O（∑param_i_size，对于所有i）相交array_pop O（πparam_i_size，对于所有i）-这是所有param_sizes的乘积array_shift O（∑ param_i_size ，因为i！= 1）-这是因为我们不需要迭代第一个数组。array_unshift O（∑ array_i，i！= 1）-不需要迭代第一个数组q4312079 q（union）O（n），其中n是第二个数组的大小（即array_first + array_second）-比array_merge更少的开销，因为它不必重新编号
array_intersect_key O（∑ array_i，对于所有i）随机数：
array_intersect O（n）array_intersect_assoc O（n）-需要线性轮询。明显的Big-O：
array_diff O（n）array_diff_key O（n）array_merge O（n）+ O（偏移量+长度）array_replace O（偏移量+长度）或O（n）如果length = NULL shuffle O（n） array_rand O（n）array_fill O（n）array_fill_keys O（pad_size）range O（ n）array_splice O（n）array_slice O（n）array_keys O（n）array_values O（n）array_reverse O（n）array_pad O（n）array_flip O（n）我要感谢Eureqa使得找到函数的Big-O很容易。这是一个了不起的免费程序，它可以为任意数据找到最佳的拟合函数。
编辑：基准测试（对于大多数实际值，它们仍然有效）。
$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 );
}
评论
@Kendall：谢谢！我做了一些阅读，结果发现PHP使用“嵌套”哈希表进行冲突。也就是说，它不是使用冲突的登录结构，而是仅使用另一个哈希表。而且我确实了解到，实际上讲PHP哈希表可提供O（1）性能，或平均至少达到O（1）-这就是哈希表的用途。我只是想知道为什么您说它们是“真正的O（n）”而不是“真正的O（logn）”。好的文章！
–凸轮
2011年6月11日8:32
时间复杂度应包含在文档中！选择正确的功能可以节省您很多时间，或者告诉您避免执行您打算做的事情：p已经感谢您的清单！
–塞缪尔
2012年6月9日23:38
我知道这很旧...但是什么？该曲线根本不显示O（n），而是显示O（log n），en.wikipedia.org / wiki /对数。对于嵌套哈希图，这也是正确的。
–安德烈亚斯（Andreas）
13年5月5日14:58
数组元素上未设置的Big-O是什么？
–手工
14年4月30日在16:51
尽管哈希表确实具有最坏情况下的O（n）查找复杂性，但平均情况为O（1），基准测试所测试的特定情况甚至可以保证为O（1），因为它是从零开始的，连续的，数字索引的数组，永远不会发生哈希冲突。您仍然看到对数组大小的依赖性与算法复杂性无关的原因，这是由CPU缓存效应引起的。数组越大，随机访问查找就越有可能导致缓存未命中（并且层次结构中的缓存未命中率更高）。
– NikiC
16年1月28日在16:54
#2 楼
您具体描述的情况的解释是关联数组被实现为哈希表-因此按键查找（和array_key_exists对应）为O（1）。但是，数组不是按值索引的，因此通常情况下，发现数组中是否存在值的唯一方法是线性搜索。在那里也就不足为奇了。我认为没有关于PHP方法的算法复杂性的具体综合文档。但是，如果有足够大的顾虑需要付出努力，则可以随时查看源代码。
评论
这不是真正的答案。正如我在问题中所说的，我已经尝试研究PHP源代码。由于PHP是用复杂的宏用C语言编写的，因此有时很难“看清”底层的函数。
–肯德尔·霍普金斯（Kendall Hopkins）
10 Mar 18 '10在23:30
@Kendall我忽略了您对深入源代码的引用。但是，我的答复中有一个答案：“我认为没有关于PHP方法算法复杂性的具体综合文档。” “否”是一个完全有效的答案。 （C：
–达森（Dathan）
10 Mar 19 '10在0:08
#3 楼
您几乎总是想使用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秒当然，这并不显示时间复杂度，但是它确实显示了这两个功能之间的比较。
要测试时间复杂度，请比较在第一个键和最后一个键上运行这些功能之一所花费的时间。 br />
评论
错了我100％确定array_key_exists不必遍历每个键。如果您不相信，请查看下面的链接。 isset之所以这么快，是因为它是一种语言构造。这意味着它没有进行函数调用的开销。另外，由于这个原因，我认为它可能正在缓存查询。另外，这不是问题的答案！我想要一个PHP函数的Big（O）列表（如问题所述）。我的示例没有一个基准。 svn.php.net/repository/php/php-src/branches/PHP_5_3/ext / ...
–肯德尔·霍普金斯（Kendall Hopkins）
10 Mar 20 '10在15:27
如果您仍然不相信我，我会创建一个小的基准来证明这一点。 pastebin.com/BdKpNvkE
–肯德尔·霍普金斯（Kendall Hopkins）
2010年3月20日16:00
基准测试的问题在于必须禁用xdebug。 =）
– Guilherme Blanco
2013年1月7日19:38
为什么要在array_key_exists上使用isset有两个关键原因。首先，isset是一种语言构造，可减轻函数调用的成本。这类似于$ arrray [] = $ append vs array_push（$ array，$ append）参数。其次，array_key_exists还区分非设置值和空值。对于$ a = array（'fred'=> null）; array_key_exists（'fred'，$ a）将返回true，而isset（$ ['fred']）将返回false。这个额外的步骤很简单，将大大增加执行时间。
–orca
2013年1月29日19:16
评论
完全不合主题，但是1不是质数。PHP中的数组是哈希表。那应该告诉您所有您需要知道的。在哈希表中搜索键是O（1）。搜索值是O（n）-您不能在未排序的集合上胜过它。您好奇的大多数功能可能都是O（n）。当然，如果您真的想知道，可以阅读源代码：cvs.php.net/viewvc.cgi/php-src/ext/standard/…
根据记录，您尝试执行的操作的最快实现是（而不是使用NULL值）使用true，然后使用isset（$ large_prime_array [$ number]）测试是否存在。如果我没记错的话，它的速度要比in_array函数快数百倍。
Big O符号与速度无关。与限制行为有关。
@Kendall我没有将其与array_key_exists进行比较，而是将其与in_array进行了比较。 in_array迭代数组中的每个项目，并将该值与您传递给它的指针进行比较。如果将值翻转为键（并且仅将每个值替换为虚拟值（如true），则使用isset的速度要快很多倍。这是因为数组的键由PHP索引（如哈希表）。 ，以这种方式搜索数组可以大大提高速度。