После некоторого времени использования PHP я заметил, что не все PHP встроили функции так быстро, как ожидалось. Рассмотрим две ниже возможные реализации функции, которая находит, является ли число простым, используя кэшированный массив простых чисел.

//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 реализован линейный поиск O (n), который будет линейно замедляться как$prime_array растет. Гдеarray_key_exists Функция реализована с помощью поиска хеша O (1), который не будет замедляться, если хеш-таблица не будет заполнена слишком сильно (в этом случае это только O (n)).

До сих пор мне приходилось открывать big-O методом проб и ошибок, а иногда иглядя на исходный код, Теперь к вопросу ...

Был ли список теоретических (или практических) больших значений O для всех * встроенных функций PHP?

* или хотя бы интересные

Например, мне очень трудно предсказать, какой большой O функций указан в списке, потому что возможная реализация зависит от неизвестных базовых структур данных PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace (с входами в массив) и т. Д.