什么是相同算法的这两个实现的大哦？

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

第一个使用hashmap：

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）是正确的吗？

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

---

第一个实现的大哦是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;
}

链接地址: http://www.djcxy.com/p/40067.html

上一篇: What is the Big Oh of these two implementations of the same algorithm?

下一篇: How is python's difflib.find