Javascript 中 unshift() 与 push() 的时间复杂度 [英] Time complexity of unshift() vs. push() in Javascript

问题描述

我知道 JavaScript 中 unshift() 和 push() 方法有什么区别，但我想知道时间复杂度有什么区别?

我想 push() 方法是 O(1) 因为你只是在数组的末尾添加一个项目，但我不确定 unshift() 方法，因为，我想您必须向前移动"所有其他现有元素，我想这是 O(log n) 或 O(n)?

解决方案

据我所知，JavaScript 语言规范没有强制要求这些函数的时间复杂度.

当然可以使用 O(1) push 和 unshift 操作来实现类似数组的数据结构(O(1) 随机访问).C++ std::deque 就是一个例子.因此，使用 C++ 双端队列在内部表示 Javascript 数组的 Javascript 实现将具有 O(1) push 和 unshift 操作.

但是如果你需要保证这样的时间界限，你就必须自己动手，像这样:

http://code.stephenmorley.org/javascript/queues/

I know what is the difference between unshift() and push() methods in JavaScript, but I'm wondering what is the difference in time complexity?

I suppose for push() method is O(1) because you're just adding an item to the end of array, but I'm not sure for unshift() method, because, I suppose you must "move" all the other existing elements forward and I suppose that is O(log n) or O(n)?

解决方案

The JavaScript language spec does not mandate the time complexity of these functions, as far as I know.

It is certainly possible to implement an array-like data structure (O(1) random access) with O(1) push and unshift operations. The C++ std::deque is an example. A Javascript implementation that used C++ deques to represent Javascript arrays internally would therefore have O(1) push and unshift operations.

But if you need to guarantee such time bounds, you will have to roll your own, like this:

http://code.stephenmorley.org/javascript/queues/

这篇关于Javascript 中 unshift() 与 push() 的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！