同一算法的这两种实现的 Big Oh 是什么

Question

我正在编写一个算法，如果字符串不包含重复字符，它将返回true，否则返回false。我有两种不同的实现：

第一个使用哈希图：

public static boolean hasUniqueCharsFast(String s) {
    char[] input = s.toCharArray();
    Map<Character, Character> map = new HashMap<Character, Character>();
    for (char c: input) {
        if (map.get(c) != null) {
            return false;
        } else {
            map.put(c, c);
        }
    }
    return true;
}

第二个是就地的，比较每个字符将每隔一个字符：

public static boolean hasUniqueChars(String s) {
        char[] input = s.toCharArray();
        //Compare the string with everything but itself (i.e. ignore chars at same index)
        for (int i=0;i<input.length;i++) {
            for (int j=0;j<input.length;j++) {
                if (input[i] == input[j] && i != j ) {
                    return false;
                }
            }
        }
        return true;
    }

第一个实现的大哦是 O（n），第二个实现的大哦是 O（n^2） 是否正确？

我想权衡是第一个使用额外的存储空间，而第二个实现不使用额外的存储空间（即就地）？

Answer 1

第一个实现的大哦是 O（n），第二个实现的大哦是 O（n^2） 是否正确？

是的。哈希操作被认为具有恒定成本。

我想权衡是第一个使用额外的存储空间，而第二个实现不使用额外的存储空间（即就地）？

是的。您还应该注意，第一个的常量值更高。但是对于大字符串，第一种算法将粉碎第二种算法。

请注意，代码可以优化为几乎两倍的速度。

第一个算法（假设put返回以前的值，就像在java中一样）：

public static boolean hasUniqueCharsFast(String s) {
    char[] input = s.toCharArray();
    Map<Character, Character> map = new HashMap<Character, Character>();
    for (char c: input) {
        if (map.put(c, c) != null) {
            return false;
        }
    }
    return true;
}

第二种算法：

public static boolean hasUniqueChars(String s) {
    char[] input = s.toCharArray();
    //Compare the string with everything but itself (i.e. ignore chars at same index)
    for (int i=0;i<input.length;i++) {
        for (int j=i+1;j<input.length;j++) {  // Changed starting index
            if (input[i] == input[j]) {       // Removed i == j check
                return false;
            }
        }
    }
    return true;
}