Блог

Сложность пространства определяется как : Auxiliary Space is the extra space or temporary space used by an algorithm.

Итак, какова сложность пространства приведенного ниже кода? Строка ввода str не добавляет дополнительного пробела, но конструктор использует некоторый пробел.

Итак, является ли сложность пространства O (1) или O (n), где n — заданный размер?

 public class AsymptoticNotationForSearch {

    private final Set<String> set;

    public AsymptoticNotationForSearch(Set<String> strSet) {
        this.set = strSet;
    }


    public boolean contains(String str) {
        return set.contains(str);
    }

}
  

Это O (1) — набор переменных — это просто ссылка на объект, пространство, которое он использует, является статическим и не зависит от размера переданного набора. Только если вы сделали копию этого набора, это будет O (n) .