数组操作的复杂性 [英] Complexity of Array Operations

问题描述

因此，我的 comp sci 课程中的主题之一是关于时间复杂度，并使用数组和链表作为比较某些操作的好方法以及哪种容器更擅长这样做，因此您可以选择合适的数据结构.我了解大多数操作背后的原因，但我不确定其中一个是在数组中插入和追加.

So one of the topics in my comp sci class is concerning time complexity and using arrays and linked lists as a good way to compare certain operations and what container is better at doing so, so you can choose the appropiate data structure. I understand the reasoning behind most of the operations but I'm unsure about one and that is inserting and appending in an array.

这两种情况的最坏情况是 O(n).我相信我理解为什么插入是 O(n) 因为最坏的情况是，你在前面插入导致你将所有元素向右移动，这意味着它是线性的并且依赖于数组中的元素数量.对于追加，我很好奇为什么不是 O(1)，因为无论大小如何，只要有空间，在最后添加元素都需要一次操作.

The worst case scenario for both of these is O(n). I believe I understand why inserting is O(n) because worst case, you insert at the front causing you to shift all elements over to the right meaning that its linear and dependent on the number of elements in the array. For appending, I was curious why it was not O(1) since it takes one operation no matter the size to add an element at the end, given that there is space.

这是不是问题，如果没有足够的空间，您必须在最坏的情况下将数组复制到更大的数组?

Is that the issue, if there isn't enough space you have to copy the array to a larger one for its worst case scenario?

推荐答案

[...] 如果没有足够的空间，您必须将数组复制到更大的数组最坏的情况?

[...] if there isn't enough space you have to copy the array to a larger one for its worst case scenario?

宾果游戏.

这篇关于数组操作的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！