Какова продолжительность выполнения 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

Вот другой SO нить, которая объясняет реализацию Array.length:

How is length implemented in Java Arrays?

Вызов свойства length является операцией O (1), так как она фактически не подсчитывает массив, это поле задается при создании массива.

С другой стороны, ваша петля является операцией O (n).

Answer 3

Это постоянная работа во всех реализациях JAVA, потому что JVM должна хранить это поле для проверки индекса (он должен вызывать IndexOutOfBoundsException, если индекс недействителен).

Может быть хорошей идеей кэшировать длину массива в локальной переменной, поскольку доступ к стеклу JVM выполняется быстрее, но это улучшение очень незначительное, обычно выполнение цикла тела будет избыточным весом этой оптимизации.