这个字符串操作代码的空间复杂性是多少？

Question

这段代码来自Cracking the Coding访谈书.

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(n),其中n是字符串的长度,空间复杂度为O(n).

我理解时间复杂度为O(n)但我不明白空间复杂度怎么可能是O(n)

我的想法:无论输入(str)大小是多少,char_set都将保持256大小的数组.即使"str"的长度为100,000,char_set仍然是256个元素的数组.所以我想,因为这个函数的内存需求不随输入的大小而变化并保持常数256,所以空间复杂度是常数,即O(1).

有人可以解释,如果我错了(为什么？)

非常感谢.

Answer 1

我认为这有点复杂：

某个字符遇到两次之前的最大迭代次数是构建字符串的字母表的大小。

如果这个大小是有限的，时间复杂度是 O(1)，如果不是，则布尔数组的大小不可能是有限的，因此，空间复杂度将为 O(n)。