Leetcode 809 时间复杂度

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        
        if (words.length == 1) return 1;
        
        String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        TreeSet<String> set = new TreeSet<>();
        
        for (String word : words) {
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < word.length(); i ++) {
                res.append(morse[word.charAt(i) - 'a']);
            }
            set.add(res.toString());
        }
        
        return set.size();
    }
}

bob老师，您课上讲的这个题目。可不可以理解，时间复杂度是O(log(N)*N)呢？因为外面的循环是遍历字符串array，内层的循环跟每个单词的长度有关，leetcode官网有如下要求:

1 <= words[i].length <= 12

既然每个word的长度不超过12，可以认为是常数？但是，TreeSet的添加操作是O(log(N))的，所以合起来是O(n * log(n))。不知道这样的理解对不对？谢谢！

讲武德的年轻人 2022-03-11

源自：二分搜索树 2-4 Leetcode中的集合问题和更多集合相关问题

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2022-03-11 10:37:43

这样理解是可以的。通常在面试的时候不会对这个“小问题”较真的。

但如果真要较真。我们可以在时间复杂度里再添加一个参数 k，表示 word 的最高长度。那么，循环内的复杂度实际上是：

O(k + klogn)。

O(k) 部分就是 i 的这个内层循环，很好理解；

O(klogn) 是 set.add 的复杂度。为什么有一个 k，因为添加的元素是字符串，每次在一个节点里比较当前节点的字符串和待插入字符串之间的大小关系，是需要比较这 k 个字符的。所以 set.add 的复杂度是 O(klogn)。

因此，整个算法的复杂度是：O(n(k + klogn))。

但因为在这个问题里，k 实在太小了（最大为 12），把他理解为 1 也没问题，那就是 O(nlogn) 的。

继续加油！：）

收起回答

讲武德的年轻人提问者 #1

谢谢老师！不过，这个算法的复杂度是不是应该：O(n(k + logn))呢？因为set的添加是针对整个word，不是单个字符？

2022-03-11 11:21:09
liuyubobobo 回复提问者讲武德的年轻人 #2

整个 set 有 n 个元素，所以比较的节点总数是 logn，在每次比较的时候都有可能有 k 次字符比较，所以是 klogn。

2022-03-11 14:11:14
讲武德的年轻人提问者回复 liuyubobobo #3

了解了，因为这里比较的是string，所以要考虑string长度，如果是int，就比较一次

2022-03-11 23:40:20