优化字谜函数的时间复杂度

Question

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

以下是吐出七字组的功能。它对每个输入单词进行排序，然后将排序后的输入单词放入字典中。我根据geeksforgeeks发布的提示自行编写了代码，该提示建议：

使用排序：我们可以对字符串数组进行排序，以便所有字谜一起来。然后通过线性遍历排序数组。该解决方案的时间复杂度为O（mnLogn）（将在排序中进行O（nLogn）比较，并且将进行比较花费O（m）的时间）。其中，n是字符串数，m是字符串的最大长度。

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

我认为以下代码的时间复杂度为n（m log m）。空间复杂度为：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），由对数组中每个字符串进行排序所需的时间决定；因此您的分析是正确的。但是，您的结果与您引用的结果不同，不是因为引用错误，而是因为您的算法与引用中分析的算法不同。请注意引号说：

我们可以对字符串数组进行排序，以便所有字谜组合在一起。

您的算法不执行此操作；它根本不对字符串数组进行排序，而是对每个字符串中的字符分别进行排序。这是此报价所讨论算法的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）时间，因为键函数需要O（m）时间并为n个字符串调用，然后按O（n log n）时间对字符串进行排序。排序中的比较是在长度为NO_OF_CHARS（常数）的列表上完成的，因此比较需要固定的时间。
• 将单词分组在一起需要O（mn）的时间，因为它被n次调用char_freqs所支配；可以通过重新使用排序中已经计算出的键将其改进为O（n），但是无论如何，这部分还是由排序决定的。]

这使整体时间复杂度为O（mn + n log n），与引用的结果不同，但是如果每次comparison

，而不是每个元素缓存一次。例如，如果您使用类似以下命令的方式在Java中进行了排序：

char_freqs
然后比较将花费O（m）时间而不是O（1）时间，并且总时间复杂度将为O（mn log n）。因此，引用没有错，它只是在谈论与您所考虑的算法不同的算法，并且假定该算法的实现不是最优的。