循环内python排序方法的时间复杂度

Question

def findEquals(words, word):
    wordCounts = sorted(Counter(word).values())
    equals = []

    for word in words:
        wordsCounts = sorted(Counter(word).values())
        if wordCounts == wordsCounts:
            equals.append(word)

    return equals

所以我在代码中有一个循环，其中words是一个单词列表。对于列表中的每个单词，我将字母在计数器中的频率存储为值，然后使用sorted（）方法进行排序。我知道sorted（）的时间复杂度是O（nlog（n））。因为sorted（）是在for循环中使用的，所以整个代码最糟糕的时间复杂度是O（n^2 log（n））？在

Answer 1

这里的渐近分析有点奇怪，因为正如你所写的，它实际上是三个输入的函数：干草堆，草堆中每个单词的长度，和指针。在

为了更简单，您可以缓存针的排序值：这些值是静态的（这个操作将被草堆中的迭代所淹没）。在

我还简化了代码以使用过滤，这将抽象出循环迭代。这不会对算法的性能产生理论上的影响，但返回迭代器将产生延迟结果，这可能会提高实际性能。在

因为频率是整数，所以它们可以按照频率的数量按^{}排序。在

因此，对于大海捞针中的每一个元素，您都将对其进行排序并与针的频率进行比较。这将是O(n*m)，其中{}是干草堆的大小，m是干草堆中每个元素的大小。在

因此，您的代码可以简化：

def find_same_frequency_distribution(haystack, needle):
    needle_counts = sorted(Counter(needle).values())
    return filter(lambda x: sorted(Counter(x).values()) == needle_counts, haystack)

^{pr2}$

Answer 2

Am I right to say that the worst time complexity of the whole code is O(n^2 log(n)) since sorted() is used inside a for loop?

不一定。for循环是O（N），而sorted是O（nlogn），但这些表达式中的“N”引用了不同的值。O（N）中的N表示words的长度，O（N logn）中的N表示word的长度。在

只有当每个word字符串的平均长度等于words列表的长度时，该算法的总复杂度为O（n2 logn）。例如，words包含五个单词，每个单词有五个字母。但不太可能是这样。更一般的结论可能是，该算法是O（m*n logn），其中m对应于words的大小，n对应于单词的平均大小。在