What is the Big Oh of these two implementations of the same algorithm?

I am writing an algorithm which will return true if a string contains no duplicate characters, and false otherwise. I have two different implementations:

The first uses a 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;
}

The second is in-place and compares each character will every other character:

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;
    }

Is it correct that the Big Oh of the first implementation is O(n), and the Big Oh of the second implementation is O(n^2)?

I guess the trade-offs are that the first one uses additional storage space, whereas the second implementation doesn't use additional storage (ie is in-place)?

---

Is it correct that the Big Oh of the first implementation is O(n), and the Big Oh of the second implementation is O(n^2)?

Yes. Hash operations are considered to have constant cost.

I guess the trade-offs are that the first one uses additional storage space, whereas the second implementation doesn't use additional storage (ie is in-place)?

Yes. You should also note that the constant value of the first is higher. But for large strings the first algorithm will crush the second.

Note that the code can be optimized to be almost twice as fast.

First algorithm (assuming put returns previous value, like in 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;
}

Second algorithm:

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/40068.html

上一篇: Python字典排序字符串的Anagram

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