What are the Time Complexities of Common PHP Built-in Array Functions?

Understanding the Time Complexity of PHP Built-in Functions

Various PHP built-in functions exhibit different time complexities when handling data structures. This article provides a comprehensive list of theoretical and practical Big-O times for these functions, enabling developers to optimize their code performance.

Interesting Points

• isset/array_key_exists: Significantly faster than in_array and array_search for lookup operations.
• (Union): Slightly faster than array_merge, offering a more concise syntax for combining arrays.
• shuffle: Possesses the same Big-O complexity as array_rand, making both functions suitable for randomizing data.
• array_pop/array_push: Faster than array_shift/array_unshift due to the penalty incurred during re-indexing.

Lookups

• array_key_exists: Effectively O(1), as hash lookup is close to instantaneous, despite its theoretical O(n) complexity.
• isset( $array[$index] ): Similar to array_key_exists, demonstrating near-constant time complexity.
• in_array: O(n), as it performs a linear search through the array.
• array_search: O(n), utilizing the same core function as in_array but returning the value.

Queue Functions

• array_push: O(∑ var_i, for all i), where var_i represents additional values passed as arguments.
• array_pop: O(1).
• array_shift: O(n), due to the re-indexing required.
• array_unshift: O(n ∑ var_i, for all i), again resulting from the necessary re-indexing.

Array Intersection, Union, Subtraction

• array_intersect_key: If intersection is 100%, O(Max(param_i_size) * ∑param_i_count, for all i); if intersection is 0%, O(∑param_i_size, for all i).
• array_intersect: If intersection is 100%, O(n^2 * ∑param_i_count, for all i); if intersection is 0%, O(n^2).
• array_intersect_assoc: Similar to array_intersect_key, exhibiting the same Big-O time complexities.
• array_diff: O(π param_i_size, for all i), representing the product of the parameter sizes.
• array_diff_key: O(∑ param_i_size, for i != 1), since it excludes the iteration over the first array.
• array_merge: O(∑ array_i, i != 1), not requiring iteration over the first array.
• (Union): O(n), where n is the size of the second array, incurring lower overhead than array_merge.
• array_replace: O(∑ array_i, for all i).

Random

• shuffle: O(n).
• array_rand: O(n), involving a linear search.

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: O(n).
• array_values: O(n).
• array_reverse: O(n).
• array_pad: O(pad_size).
• array_flip: O(n).
• array_sum: O(n).
• array_product: O(n).
• array_reduce: O(n).
• array_filter: O(n).
• array_map: O(n).
• array_chunk: O(n).
• array_combine: O(n).

The above is the detailed content of What are the Time Complexities of Common PHP Built-in Array Functions?. For more information, please follow other related articles on the PHP Chinese website!