array.length的运行时是什么？

Question

假设我有一个数组：

int[] array = new int[10];

什么是运行时：

int len = array.length;

我认为这将是一个恒定的时间操作，但今天在一次采访中，面试官告诉我这将是O(n)，因为需要计算元素的数量。

另外，如果我有一个这样的循环：

for (int i = array.length - 1; i >=0; i--) {
    something with array[i];
}

这是否需要额外的n操作才能到达数组的末尾以开始循环？面试官有C背景，所以他们可能搞错了Java的工作原理，但我不想在面试时推它。

Answer 1

array.length是O(1)，循环总体是O(n) (假设“某物”是恒定时间)。

对于c是不同的吗？

C的不同之处在于，根据数组的分配方式，您可以在O(1)时间内找到它的大小，或者根本不找它的大小。所谓“一点也不”，我的意思是你必须自己跟踪尺寸。

(就个人而言，如果这就是面试官的能力，我对来那里工作会有所保留。)

Answer 2

在所有的JAVA实现中，它都是一个固定时间的操作，因为JVM必须存储这个字段来检查索引(如果索引无效，它必须抛出IndexOutOfBoundsException )。

将数组长度缓存在局部变量中可能是一个好主意，因为JVM堆栈访问速度更快，但这种改进非常小，通常循环体执行会加重这种优化。

Answer 3

下面是另一个解释array.length实现的SO线程：

How is length implemented in Java Arrays?

调用length属性是一个O(1)操作，因为它实际上并不计算数组，该字段是在创建数组时设置的。

另一方面，您的循环是一个O(n)操作。