向数组添加一个元素的时间复杂度是多少？

Question

PHP 的数组是复杂的野兽；它们允许像普通哈希表一样快速查找，但它们的键值对也是有序的。随着现有元素数量的增加，将元素插入到该结构中的时间成本如何变化？

时间复杂度是否完全取决于我如何将元素插入数组？例如，执行以下每个操作：

array_unshift($array, $value);
array_push($array, $value);
array['some_new_key'] = $value;

具有相同的时间复杂度，还是不同的时间复杂度？

Answer 1

恒定时间 O(1)

array_push是常数时间（类似哈希表的结构的队列函数），但有趣的是，性能方面：

array_push();
$array[] = $val;

后一种方法比后一种方法更快，array_push因为无需支付开销函数调用的成本。

线性时间 O(n)

绝对array_push和相关的队列函数比array_unshift. 是的，它们都执行相同的功能，但以不同的方式来实现这一点。正如您已经注意到的，PHP 的数组非常强大并且提供了强大的功能。这是有代价的，因为 PHP 的数组有有序的键，你需要支付额外的成本来重新索引所有这些键，所以O(n). array_unshift然后将采用数组的线性时间 + 将值附加到数组头部的常数时间，因此类似于 ，O(n + cn')其中c是将元素添加到数组的常数时间，n' 是正在添加的项目数添加。