我有几个问题关于Java Collection
的add
函数如何处理字符串。例如,在下面的代码片段中,我正在将一个字符串List
复制到HashSet
中。在这种情况下,最坏情况下的总时间复杂度是多少?是O(M x N)还是O(N),其中M是列表中任何字符串的最大长度,N是列表中字符串的总数。
public HashSet<String> createDict(List<String> wordList) {
HashSet<String> wordDict = new HashSet<>();
for(String word : wordList) {
wordDict.add(word);
}
return wordDict;
}
如果我使用以下代码而不是循环,时间复杂度会完全相同吗?
HashSet<String> wordDict = new HashSet<>(wordList);
HashSet
添加元素和工作方式有关。请参见下面提供有关此信息的答案。但这是现实的答案。您可以认为必须至少读取长度M一次。逐个字符进行读取,如果对于每个n都这样做,则复杂度确实为O(M x N)。但这是“我非常严肃地采用O符号表示法”的答案。 - akuzminykh