这两种算法比较？

Question

所以我遇到了一个问题."确定字符串是否包含所有唯一字符"

所以我编写了这个解决方案,将每个字符添加到一个集合中,但如果该字符已经存在,则返回false.

private static boolean allUniqueCharacters(String s) {

    Set<Character> charSet = new HashSet<Character>();
    for (int i = 0; i < s.length(); i++) {
        char currentChar = s.charAt(i);
        if (!charSet.contains(currentChar)) {
            charSet.add(currentChar);

        } else {
            return false;
        }

    }
    return true;

}

根据我正在阅读的书,这是"最佳解决方案"

public static boolean isUniqueChars2(String str) {
    if (str.length() > 128)
        return false;

    boolean[] char_set = new boolean[128];

    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(1)它们不会是相同的复杂性？

谢谢.

Answer 1

正如Amadan在评论中所说的那样,这两个解决方案具有相同的时间复杂度O(n),因为你有一个for循环遍历字符串,并且你在for循环中进行常数时间操作.这意味着运行方法所需的时间随着字符串的长度线性增加.

请注意,时间复杂性是指在更改输入大小时所需的时间变化.这不是关于相同大小的数据有多快.

对于相同的字符串,"最佳"解决方案应该更快,因为集合在数组上有一些开销.处理数组比处理集更快.但是,要实际使"最佳"解决方案有效,您需要一个长度为2 ^ 16的数组.这就是char有多少不同的值.您还需要删除检查长度超过128的字符串.

这是空间和时间之间权衡的众多例子之一.如果你想要它更快,你需要更多的空间.如果你想节省空间,你必须放慢速度.