计算使用HashTable的算法的复杂度

吉姆·贝鲁希2

我需要计算使用的算法的复杂度HashTables。应该是O(logn)，正确吗？HashTables当我计算复杂度时，更改的用法会有所变化吗？

protected static int distanceDyn(String s1, String s2, Hashtable <Pair<String, String>, Integer> dictionary) {
    int no_op, min;
    if (dictionary.containsKey(new Pair<String, String>(s1, s2)))
        return dictionary.get(new Pair<String, String>(s1, s2));

    if (s1 == null || s2 == null) throw new IllegalArgumentException();

    if (s1.length() == 0) {
        dictionary.put(new Pair<String, String> (s1, s2), s2.length());
        return s2.length();
    }

    if (s2.length() == 0) {
        dictionary.put(new Pair<String, String> (s1, s2), s1.length());
        return s1.length();
    }

    if (s1.charAt(0)==s2.charAt(0)) no_op = distanceDyn(s1.substring(1), s2.substring(1), dictionary);
    else no_op = -1;

    int del = 1 + distanceDyn(s1, s2.substring(1), dictionary);
    int ins = 1 + distanceDyn(s1.substring(1), s2, dictionary);
    if (no_op == -1) {
        dictionary.put(new Pair<String, String> (s1, s2), Math.min(del, ins));
        return Math.min(del, ins);
    } else 
    min = Math.min(del, Math.min(ins, no_op));
    dictionary.put(new Pair<String, String> (s1, s2), min);
    return min;
}

凯杜尔

从您的代码看来，它是用于编辑距离算法的动态编程方法。

首先，对编辑距离的动态规划方法的复杂性是O(n * m)在那里n和m两个字符串的长度，它不可能在任何地方接近O(logn)。

其次，这里HashTable已经使用了。如果是a HashMap，则对的操作HashMap不会影响总复杂度的计算，因为插入/搜索已摊销O(1)。对于哈希表，它会慢一点，因为它HashTable是线程安全的。对于这个问题，我认为没有必要使用HashTable代替HashMap。但是，渐近而言，复杂度仍然存在O(n * m)。