PHP:函数'count'的复杂性[即O(1),O(n)]是多少？

Question

count()数组函数的Big-O时间复杂度是多少？

例

$x = array(1,2,3);
echo count($x); // how many operation does it takes to count the elements 
                // of the array? is it 3, or is it 1

Answer 1

$ time php -r '$a=range(1,1000000); $b=0; for($i=0;$i<10;$i++) $b=count($a);'
real    0m0.458s
$ time php -r '$a=range(1,1000000); $a=array(1); $b=0; for($i=0;$i<10;$i++) $b=count($a);'
real    0m0.457s

对我来说似乎很漂亮O(1).

经过测试的PHP版本: PHP 5.3.3-1ubuntu9.1 with Suhosin-Patch (cli) (built: Oct 15 2010 14:00:18)

Answer 2

数组具有O(1)大小 - 也就是说,它们的大小存储在某处.该语言更新插入/删除的计数.