PHP: Какова сложность [i.e O (1), O (n)] функции "count"?

Какова сложность времени Big-O функции count() для массивов?

Пример

$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

Ответы

Ответ 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

Seems pretty O(1) to me.

Протестированная версия PHP: PHP 5.3.3-1ubuntu9.1 with Suhosin-Patch (cli) (built: Oct 15 2010 14:00:18)

Ответ 2

Массивы имеют размер O (1), то есть их размер где-то сохраняется. Язык обновляет количество вставки/удаления.

Ответ 3

Если вы хотите узнать источник подсчета, на него ответил другой поток: Является ли функция count count count() O (1) или O (n) для массивов?

Вот ответ:

PHP_FUNCTION(count) вызывает php_count_recursive(), который в свою очередь вызывает zend_hash_num_elements() для нерекурсивного массива, который реализован следующим образом:

ZEND_API int zend_hash_num_elements(const HashTable *ht)
{
    IS_CONSISTENT(ht);

    return ht->nNumOfElements;
}

Итак, вы можете видеть, это O(1) для $mode = COUNT_NORMAL.