Эта часть кода взята из книги «Разбивка кодирования».Какова пространственная сложность этого кода манипуляции строкой?
public static boolean isUniqueChars2(String str) {
boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[val] = true;
}
return true;
}
И автор упоминает, что
Время сложность O (п), где п длина строки, и пространство сложность O (п).
Я понимаю сложность поры до времени О (п), но я не понимаю, как может пространство сложность быть O (п)
Мое мышление: char_set останется массив размером 256 независимо от того, что в ввод (str) размер есть. Даже если длина «str» равна 100 000, char_set по-прежнему представляет собой массив из 256 элементов. Итак, я думал, поскольку требования к памяти для этой функции не изменяются с размером ввода и остаются константой 256, сложность пространства постоянна, то есть O (1).
Может кто-то объяснить, если я не прав (а почему?)
Спасибо так много.
Я думаю, что вы правы, но автор сказал, что оригинальная самооценка O (n) (или вы получаете копию по значению?). – qPCR4vir
hmmm ... это интересно. Я думал, что при выводе асимптотических сложностей мы обычно игнорируем, как/где /, когда ввод считывается? И просто сосредоточьтесь на том, что происходит внутри метода (с учетом размера ввода, который равен n) – anakkala
Хотелось бы видеть рассуждения автора. Пространство, используемое самим алгоритмом, является постоянным. Вы правы в том, что когда мы анализируем сложность пространства, мы говорим о количестве * дополнительного * пространства, необходимого для обработки, игнорируя входной сигнал алгоритма. –