为什么此算法检查数组是否具有所有唯一字符的复杂度为 space O(n)？

Question

在“Cracking the Coding Interview”一书中，第一个练习是“实现一个算法来确定一个字符串是否具有所有唯一字符（不使用额外的数据结构）”。以及解决方案：

public static boolean isUniqueChars(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是字符串的长度，space复杂度是O(n)”。

我不明白为什么 space 复杂度是 O(n)。数组 char_set 具有恒定长度，与给定 str 的长度无关。对我来说，space 复杂度是 O(1)。

Answer 1

它的 space 复杂度是 O(1) (\Theta(1))，因为它比输入数组的大小多了 256（常量）位。此外，时间复杂度为 O(1)，因为输入字符串中有 256 个字符需要检查，并且最多会在字符串的第 256 个字符处检测到重复项。

为什么此算法检查数组是否具有所有唯一字符的复杂度为 space O(n)？

Why is the space complexity for this algorithm to check if an array has all unique characters O(n)?

java

algorithm

space-complexity