代码之家 › 专栏 › 技术社区 › JimBelushi2

计算使用哈希表的算法的复杂性

time-complexity algorithm java

JimBelushi2 · 技术社区 · 7 年前

我需要计算这个算法的复杂性,它使用 HashTables . 应该是 O(logn) ,是否正确?是否使用 散列表 当我计算复杂度的时候改变什么?

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

2 回复 | 直到 7 年前

Kaidul 7 年前

从您的代码来看,它似乎是编辑距离算法的动态编程方法。

首先,编辑距离的动态规划方法的复杂性是 O(n * m) 在哪里? n 和 m 两个字符串的长度是否可能接近 O(logn) .

其次,这里是 HashTable 已被使用。如果是一个 HashMap ,操作 哈希图 不会影响总复杂度计算,因为插入/搜索是分摊的 O(1) . 对于hashtable,它会慢一点,因为 散列表 是线程安全的。对于这个问题,我不认为有必要使用 散列表 而不是 哈希图 . 然而,渐进地,复杂性仍然是 O(N*m) 不管怎样。

oreh 7 年前

似乎这个算法找到了两个字符串之间的距离。的复杂性 put() 和 get() 方法 Hashtable 是 O(1) ,但这里使用递归。所以 distanceDyn() 将调用方法 kN 最坏情况下的时间,其中 N 等于 s1 和 s2 和 k 是一个常量。就渐进复杂性而言 O(N) 因为系数没有考虑在内。