为什么该算法检查一个数组是否全部具有唯一字符O(n)？

Question

在“破解编码面试”一书中，第一个练习说“实现一个算法来确定一个字符串是否都具有唯一的字符(不使用额外的数据结构)”。解决方案是：

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是字符串的长度，空间复杂度是O(n)”。

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

Answer 1

它的空间复杂度是O(1) (\Theta(1))，因为它保持比输入数组大小多256 (常量)位。而且，时间复杂度是O(1)的，因为在输入字符串中有256个字符要检查，并且最多将检测到字符串的第256个字符的重复。