我有一个由10个元素组成的数组。Integer[]arr=新整数10；当我添加第五个元素，如arr[5]=999；时，时间复杂度是多少；。我坚信数组中插入的时间复杂度是O(1(，但在一些文献中，对于数组(而不是数组列表(上的插入，T。C是O(N(，因为发生了移位。怎么会发生转变？它不是动态数组。
这里的来源，我认为他们是错误的：
- 大O符号数组与链表插入
O(1(准确地描述了在数组末尾的插入。然而如果要插入数组的中间，则必须将所有该元素之后的元素，因此插入的复杂性对于阵列，这种情况是O(n(。末尾附加也会对案例进行折扣如果数组已满，则必须调整其大小。
- https://iq.opengenus.org/time-complexity-of-array/
插入和删除元素需要线性时间，具体取决于实施如果我们想要在特定索引处插入元素，我们需要将该索引中的所有元素向右跳过一个位置这需要线性时间O(N(。
3。https://www.log2base2.com/data-structures/array/insert-element-particular-index-array.html
如果我们想插入一个元素到索引0，那么我们需要将所有元素向右。
例如，如果我们在数组中有5个元素，并且需要插入元素，我们需要将这5个元素全部移到一个位置向右。
有一个误解：
arr[5]=999;是一个直接的赋值，而不是会发生移位的"插入"，所以是的：它是O(1(
插入另一方面包括以下步骤：
- 如果数组已满，请创建一个新数组
-
- 并将索引(<(下的数据复制到0
- 将索引(>=(以上的数据复制到
index + 1 - 赋值
arr[index]=newValue;
所以插入，因为它必须在每个插入上复制/移动n-index元素，所以被认为是O(n(，因为大oh符号是为了展示最坏的情况而设计的。
现在，有了MXX寄存器和GPU上的并行流水线之类的东西，我们可以通过另一个大的(常数(因素来加快速度，但问题本身仍然属于O(n(类。
不要与其他答案争论，但我认为OP询问了对数组arr[5]=999;的直接赋值。此操作将值999分配给数组中的第五个索引(如果数组长度为6或更大(。它不会进行任何转移或分配。对于这种操作，概念肯定是O(1(
在数组中插入数据有两种用例。
- 就地更换
- 移位数据
在第一种情况下(就地替换(，我们通常有类似arr[5] = 99的代码。对于这个用例，我们不打算将索引5的数据转移到索引6，依此类推。因此，这种操作的时间复杂度是O(1)。
而在第二种情况(移位数据(中，对于在索引5处插入数据，我们将首先将索引5的数据移位到索引6，并将索引6的数据移位至索引7，依此类推。在这种情况下，这种操作的时间复杂度将为O(N)