Временная сложность набора в Java

Может ли кто-нибудь рассказать мне о временной сложности приведенного ниже кода?

a - это массив из int.

Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
    if (set.contains(arr[i])) {
        System.out.println("Hello");
    }
    set.add(arr[i]);
}

Я думаю, что это O (n), но я не уверен, поскольку он использует Set, и это также содержит методы. Он также вызывает метод add Set.

Может ли кто-нибудь подтвердить и объяснить, что такое сложность во времени всего кода выше? Кроме того, сколько места потребуется?

Ответы

Ответ 1

Я считаю, что его O (n), потому что вы перебираете массив, а contains и add должны быть постоянными, потому что их хэш-набор установлен. Если бы он не был основан на хеш-основе и требовал итерации по всему набору для поиска, верхняя граница была бы равна n ^ 2.

Целые являются неизменяемыми, поэтому сложность пространства будет 2n, что, по моему мнению, упрощает только n, поскольку константы не имеют значения.

Если у вас есть объекты в массиве и установлены, тогда у вас будет 2n ссылок и n объектов, поэтому вы находитесь на 3n, что по-прежнему является линейным (временным) пространственным ограничением.

EDIT-- yep "Этот класс предлагает постоянную производительность по времени для основных операций (добавлять, удалять, содержать и размер), предполагая, что хэш-функция правильно распределяет элементы среди ковшей."

см. здесь.