java - Java 数组中的 add 和 element 的时间复杂度是多少？

Question

您好，我正在对此进行研究，但我在 Oracle 网站上找不到任何内容。

下一个问题是。

如果您使用这样的静态数组

int[] foo = new int[10];

并且您想为这种方式的 4 位置添加一些值

foor[4] = 4;

这不会移动数组的元素，因此时间复杂度将为 O(1)，因为如果数组从 0x000001 开始，有 10 个空格，并且您希望将一些空格放在可以通过 (x*sizeOf(int))+initialMemoryPosition 访问的 x 位置(这是伪代码)

对吗，这种类型的数组在java中是这样工作的吗，时间复杂度是O(1)

谢谢

Answer 1

这个问题基于一个误解:在 Java 中，您不能添加元素到数组中。

最初，数组会分配一次，并具有预定义的条目数。以后无法更改该号码。

换句话说:

int a[] = new int[5];
a[4] = 5;

不添加任何东西。它只是在内存中设置一个值。

因此，如果有的话，我们可以说我们以某种方式“O(1)”来访问内存中的地址，因为与数组相关的任何内容都不取决于条目的数量。

注意:如果您询问ArrayList，情况会有所不同，因为这里添加到数组的末尾可以导致创建一个新的、更大的(底层)数组和数据移动。