如何计算这段文档连续词统计代码的时间复杂度及优化方案？

先明确几个核心变量：

• 设所有文档的总词数为N，单个词的平均长度为L；
• HashMap的平均查找/插入操作时间为O(1)，最坏情况（哈希冲突严重，退化为链表）为O(M)，M是哈希表中已存的键值对数量。

你的代码核心逻辑是遍历所有文档中的连续词对，总循环次数约为N次（忽略文档数量带来的微小差值）。每次循环的关键操作：

1. 字符串拼接：doc.get(i)+doc.get(i+1)的时间复杂度为O(L1+L2)，L1、L2是两个词的长度，平均为O(L)；
2. 哈希表compute操作：平均情况O(1)，但哈希计算需要遍历拼接后字符串的所有字符，时间为O(L)；最坏情况哈希冲突时，操作时间升级为O(M)。

综上：

• 平均时间复杂度为O(N*L)：与所有文档中所有词的总字符数成正比；
• 最坏时间复杂度为O(NL + NM)：仅在哈希冲突极端严重时出现，实际场景中概率极低。

1. 用自定义Pair类替代字符串拼接作为哈希键 #

字符串拼接会生成大量临时String对象，既增加内存开销，又带来额外的字符遍历（拼接和哈希计算都要遍历字符）。可以用自定义WordPair类存储词对，重写equals和hashCode方法：

import java.util.Objects;

class WordPair {
    private final String first;
    private final String second;

    public WordPair(String first, String second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        WordPair that = (WordPair) o;
        return first.equals(that.first) && second.equals(that.second);
    }

    @Override
    public int hashCode() {
        return Objects.hash(first, second);
    }
}

修改后的核心代码：

HashMap<WordPair, Integer> counter; // 已初始化

public void add(ArrayList<ArrayList<String>> documents){
    for(ArrayList<String> doc : documents){
        int docLen = doc.size();
        for(int i=0; i<docLen-1; i++){ // 修正原代码中doc.size-1的语法错误
            WordPair pair = new WordPair(doc.get(i), doc.get(i+1));
            counter.compute(pair, (k,v) -> v == null ? 1 : v + 1);
        }
    }
}

这种优化的优势：

• 避免创建拼接字符串，减少内存临时对象开销；
• 哈希计算直接复用原字符串的哈希值，无需遍历拼接后的长字符串；
• 相等性对比只需分别比较两个字符串，逻辑更高效。

2. 提前缓存文档长度 #

循环中多次调用doc.size()虽为O(1)操作，但提前缓存文档长度可减少方法调用次数（极端大数量场景下有微小收益），如上面代码中int docLen = doc.size()的写法。

3. 选用现成高效Pair实现（可选） #

如果不想自定义类，可直接使用Google Guava的ImmutablePair或Apache Commons的Pair类，这些类已实现标准的equals和hashCode方法，避免重复造轮子。

内容的提问来源于stack exchange，提问作者salimski