运行时 此字符串算法的复杂性

Question

给定字符串 a 和 b，我试图理解 charDifference 方法的大 O：

public static int charDifference(String first, String second) {
    int steps = 0;
    HashMap<Character, Integer> first_histogram = getFrequencies(first);
    HashMap<Character, Integer> second_histogram = getFrequencies(second);
    Set<Character> first_keys = first_histogram.keySet(); // O(N)
    Set<Character> second_keys = second_histogram.keySet(); // O(N)
    // get first_histogram keys and loop through second_histogram to see what the differences are
        // add differences to steps
    for (char first_char : first_keys){
        int first_count = first_histogram.get(first_char);
        if (second_histogram.containsKey(first_char)){
            int second_count = second_histogram.get(first_char);
            if (first_count > second_count){
                steps += first_count - second_count;
            } else if (first_count < second_count){
                steps += second_count - first_count;
            }
        } else {
            steps += first_count;
        }
    }
    // if this key isn't in second_histogram, then add the count to steps
    // loop through second_histogram keys and if the key isn't in first_histogram, add the count to steps
    for (char second_char : second_keys){
        int second_count = second_histogram.get(second_char);
        if (!(first_histogram.containsKey(second_char))){
            steps += second_count;
        }
    }
    return steps;
}
private static HashMap<Character,Integer> getFrequencies(String str) {
    HashMap<Character, Integer> histogram = new HashMap<Character,Integer>();
    for (int i = 0; i < str.length(); i++){
        char current = str.charAt(i);
        if (histogram.containsKey(current)){
            int count = histogram.get(current);
            histogram.put(current, count+1);
        } else {
            histogram.put(current, 1);
        }
    }
    return histogram;
}

我得到了 O(N^2(，因为我为两个字符串调用 getFrequency 函数，并遍历每个集合以更新steps变量。这是对的吗？我能做些什么来降低复杂性？

Answer 1

回答您的实际问题(不是我在字里行间读到的问题！

1. 您的分析不正确，因为它甚至没有定义N.即使假设这是输入的长度，它仍然会回避应该使用哪个输入的问题，如前所述，因为涉及两个序列。

2. 为了降低复杂性的上限，您可以使用基于树的映射而不是哈希映射。前者可以为您提供 O(log n( 用于查找，而后者需要 O(n(。

我想这对你没有太大帮助，即使它回答了你的问题。我会考虑问你真正关心的是什么，但你必须先下定决心。例如，询问某事是否正确是没有帮助的。解释你的分析并询问其他人在哪一点上不正确会更聪明。