常见 PHP 数组函数的 Big-O 时间复杂度是多少？

PHP 函数的 Big-O

使用 PHP 时，各种内置函数的效率可能会有很大差异。本文旨在深入了解他们的理论（或实践）大 O 时间。

查找

• array_key_exists：O(n)，但实际上接近由于哈希查找，时间复杂度为 O(1)。
• isset($array[$index]): O(n)，也由于哈希查找，接近 O(1)。
• in_array：O(n)，比基于哈希的查找慢。
• array_search：O(n)，与 in_array 类似。

队列函数

• array_push: O(Σ var_i, for all i)
• array_pop: O(1)
• array_shift: O(n), re -索引键。
• array_unshift: O(n Σ var_i, for所有 i)，由于重新索引而变慢。

数组交集、并集、减法

• array_intersect_key: O(Max(param_i_size)* Σparam_i_count，对于所有 i) 如果交集是100%。
• array_intersect：O(n^2*Σparam_i_count，对于所有 i)，如果交集为 100%。
• array_intersect_assoc：与 array_intersect_key 类似。
• array_diff： O(π param_i_size, 对于所有 i)，所有参数的乘积大小。
• array_diff_key: O(Σ param_i_size, for i != 1)。

随机

• 随机播放：O (n)
• array_rand： O(n)

明显的 Big-O

• array_fill: O(n)
• array_fill_keys: O(n)
• 范围： O(n)
• array_splice: O(偏移长度)
• array_slice: O(偏移长度) 或 O(n) 如果长度为 NULL
• array_keys: O(n )
• 数组值： O(n)
• array_reverse: O(n)

注意

1. 所有计算均假设哈希查找为 O(1 ).
2. 渐近性能可能会因具体实现细节和输入而异data.
3. 数组是从零开始的，因此 array_push 会推送到数组末尾。

以上是常见 PHP 数组函数的 Big-O 时间复杂度是多少？的详细内容。更多信息请关注PHP中文网其他相关文章！