algorithm - 构造函数中完成的工作是否考虑了方法的时间复杂度？

Question

下面是查找输入字符串的“所有”字谜的代码。大部分工作在构造函数中完成，方法本身做的很少。

public class AllAnagramFInd {

    private final Map<String, String> dictionary;
    private Map<String, List<String>> anagramMap;

    public AllAnagramFInd(Map<String, String> dictionary) {
        this.dictionary = dictionary;
        anagramMap = new HashMap<>();
        createAnagramSignatures();
    }

    private void createAnagramSignatures() {
        for (Entry<String, String> entry : dictionary.entrySet()) {
            String string = entry.getKey();
            String signature = getSignature(string);      
            if (anagramMap.containsKey(signature)) {
                anagramMap.get(signature).add(string);
            } else {
                List<String> anagrams = new ArrayList<>();
                anagrams.add(string);
                anagramMap.put(signature, anagrams);
            }
        }
    }

    private String getSignature(String str) {
        char[] ch = str.toCharArray();      // returns a new arrayby Array.copy
        Arrays.sort(ch);    
        String sortedString = new String(ch);   // createa a new string object by Array.copy
        return sortedString;
    }

    public List<String> getAnagram(String str) {
        String signature = getSignature(str);
        if (anagramMap.containsKey(signature)) {
            return Collections.unmodifiableList(anagramMap.get(signature));
        }
        return Collections.EMPTY_LIST;
    }
}

此处的构造函数复杂度为 O(m * nlogn)，其中 m 是字典中的单词数，n 是每个单词的最大长度。

getAnagram 方法本身的时间复杂度为 O(n log n)，其中 n 是字符的最大长度。

那么我的算法的复杂度是多少？构造函数是否在解释复杂性方面发挥作用？

Answer 1

这取决于您是考虑整个过程或算法的复杂性，还是仅考虑每个方法的复杂性。对我来说这两种方法都是有效的:

getAnagram 的复杂度 -> O(n log n)

createAnagramSignatures 的复杂度 -> O(m * nlogn)

或

整个过程或算法的复杂度 -> O(n log n) + O(m * nlogn) = O(m * nlogn)