Является ли объявление массива операцией линейного времени или операцией постоянного времени?

boolean[] arr = new boolean[n];

Какова временная сложность вышеуказанной инициализации? Это O(1) или O(n)? Я думаю, что это O (1), потому что программа просто запрашивает у JVM блок памяти размером n. Как в этом случае JVM (горячая точка) фактически распределяет память?

До сих пор я просматривал следующие ссылки, однако ответ мне не ясен:

Thread-1 Thread-2


java time-complexity big-o jvm-hotspot
person bp4D    schedule 18.05.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Я думаю, что в общем это O(n), так как объявленный массив должен быть нулевым со значениями по умолчанию, в вашем случае с false.

Но ВМ также может доказать, что этот массив не читается сразу, то есть кто-то сначала записывает в него все элементы и только после этого их читает. В таком случае сложность будет O(1), потому что вы на самом деле ничего не делаете (значения по умолчанию не помещаются внутрь самого массива) - таким образом, константа.

Это, например, то, что происходит в java-11 с Collection::toArray вроде через:

default <T> T[] toArray(IntFunction<T[]> generator) {
    return toArray(generator.apply(0));
}

Итак, когда у вас есть что-то вроде:

List.of(1, 2, 3, 4)
    .toArray(x -> new Integer[x]);

Реализация на самом деле будет выполнять new Integer[0] и использовать это в сочетании с некоторым System.arrayCopy вместо предполагаемого new Integer[4]. Это делается потому, что виртуальная машина может доказать, что обнуление не требуется, поэтому пропустить его полностью.

person Eugene    schedule 18.05.2019
comment
Спасибо, @Eugene за рецензию и ссылку. По сути, анализ временной сложности (операции со структурой данных) должен учитывать и учитывать любые новые объявления массивов, когда оставшиеся члены в полиноме лучше, чем O (n)? - person bp4D; 19.05.2019
comment
Сегодня с HotSpot этого может и не случиться, но, в принципе, также существует вероятность того, что JVM пропустит обнуление, когда узнает, что свежая новая память уже обнулена. Например. некоторые операционные системы позволяют запрашивать обнуленную память при выделении новой памяти, потому что они все равно обнуляют страницы по соображениям безопасности. - person Holger; 20.05.2019
comment
@Holger или даже с AlwaysPreTouch может быть. Хорошая точка зрения - person Eugene; 20.05.2019