What are the Big-O Notations for Common PHP Array Functions?

List of Big-O for PHP Functions

PHP built-in array functions can vary significantly in their time complexity, and understanding their Big-O helps optimize code performance. Through benchmarks and code analysis, a comprehensive list of Big-O for various array_* functions has been compiled:

Lookups

• array_key_exists/isset: O(n) (practically close to O(1))
• in_array/array_search: O(n)

Queue Functions

• array_push: O(∑ var_i, for all i)
• array_pop: O(1)
• array_shift: O(n)
• array_unshift: O(n ∑ var_i, for all i)

Intersection, Union, Subtraction

• array_intersect_key (100% intersection): O(Max(param_i_size) * ∑param_i_count, for all i)
• array_intersect (100% intersection): O(n^2 * ∑param_i_count, for all i)
• array_intersect_assoc (100% intersection): O(Max(param_i_size) * ∑param_i_count, for all i)
• array_diff: O(π param_i_size, for all i)
• array_diff_key: O(∑ param_i_size, for i != 1)
• array_merge: O(∑ array_i, i != 1)
• • (union): O(n), where n is the size of the second array
• array_replace: O(∑ array_i, for all i)

Random

• shuffle: O(n)
• array_rand: O(n)

Obvious Big-O

• array_fill: O(n)
• array_fill_keys: O(n)
• range: O(n)
• array_splice: O(offset length)
• array_slice: O(offset length) or O(n) if length = NULL
• array_keys/values/reverse: O(n)
• array_pad: O(pad_size)
• array_flip: O(n)
• array_sum/product/reduce/filter/map/chunk/combine: O(n)

Note on Array Lookups

While array lookups in PHP are theoretically O(n), they behave effectively like O(1) for most practical values. Benchmarking confirms this behavior, with a time increase of only around 50% between N=1 and N=1,000,000 lookups.

The above is the detailed content of What are the Big-O Notations for Common PHP Array Functions?. For more information, please follow other related articles on the PHP Chinese website!