优化的 Anagram 函数的时间复杂度

Question

这不是作业题。我正在准备面试，并且已经对此 post 上的链接进行了大量研究。我根据建议编写了一个解决方案，但我不同意所提出的时间复杂度。我想知道我的断言是否 incorrect/correct 。

下面是吐出一组字谜的函数。它对每个输入词进行排序，并将排序后的输入词放入字典中。我根据 geeksforgeeks 帖子的提示自己编写了代码，建议：

Using sorting: We can sort array of strings so that all anagrams come together. Then print all anagrams by linearly traversing the sorted array. The time complexity of this solution is O(mnLogn) (We would be doing O(nLogn) comparisons in sorting and a comparison would take O(m) time). Where n is number of strings and m is maximum length of a string.

我不同意提到的时间复杂度

我认为以下代码的时间复杂度是 n(m log m)。 Space 复杂度为：O(2n)= O(n) 结果和 sorted_dict 变量

n=单词数，m=一个单词中的字符数

def groupAnagrams(strs):
  sorted_dict ={}
  results=[]
  for each in strs:#loop: O(n)
     #time complexity for sort: O(m log m). 
     sorted_str = "".join(sorted(each.lower())) #O(m) 
     if  not sorted_dict.get(sorted_str):  #0(1)
         sorted_dict[sorted_str] = []
     sorted_dict[sorted_str].append(each) #0(1)

  for k,v in sorted_dict.items(): #0(n)
     results.append(v)
  return results

Answer 1

你的算法的时间复杂度为 O(mn log m)，主要是对数组中的每个字符串进行排序所花费的时间；所以你的分析是正确的。但是，您的结果与您引用的结果不同，不是因为引用错误，而是因为您的算法与引用中分析的算法不同。请注意引述说：

We can sort array of strings so that all anagrams come together.

你的算法不这样做；它根本不对字符串数组进行排序，而是单独对每个字符串中的字符进行排序。这是此引用所谈论的算法在 Python 中的一个实现：

from itertools import groupby

NO_OF_CHARS = 256

def char_freqs(word):
    count = [0] * NO_OF_CHARS
    for c in word: 
        count[ord(c)] += 1
    return count

def print_anagrams_together(words):
    words = sorted(words, key=char_freqs)
    for _, group in groupby(words, key=char_freqs):
        print(*group, sep=', ')

时间复杂度可以这样确定：

char_freqs 由于遍历长度为 m 的字符串，因此需要 O(m) 时间。
排序耗时O(mn + n log n)，因为key函数耗时O(m)，对n个字符串调用，然后在O(n log n)时间内对字符串进行排序。排序中的比较是在长度为 NO_OF_CHARS（常数）的列表上完成的，因此比较需要常数时间。
将单词组合在一起需要 O(mn) 时间，因为它主要是通过再次调用 char_freqs n 次；这可以通过重用排序中已经计算的键来改进到 O(n)，但这部分无论如何都是由排序决定的。

这给出了 O(mn + n log n) 的总体时间复杂度，这与引用的不同，但如果调用关键函数 char_freqs，您将得到 O(mn log n)对于每个比较，而不是每个元素一次并缓存。例如，如果您在 Java 中使用如下内容进行排序：

// assuming that charFreqs returns something comparable
Collections.sort(words, Comparator.comparing(Solution::charFreqs));

那么比较将花费 O(m) 时间而不是 O(1) 时间，并且总体时间复杂度将是 O(mn log n)。所以引用并没有错，它只是在谈论一种与您正在考虑的算法不同的算法，并且假设它的实现不是最优的。

优化的 Anagram 函数的时间复杂度

Time complexity of an optimized anagram function

complexity-theory

big-o

time-complexity