ループ内の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 

私は単語が単語のリストである私のコードの中にこのループを持っています。リストの各単語について、カウンタの文字の頻度を値として格納し、sorted（）メソッドを使用してソートします。 sorted（）はO（nlog（n））の最悪の時間複雑さを持っていることが分かります。 forループの中でsorted（）が使われているので、コード全体の最悪の時間複雑さはO（n^2 log（n））だと言うのは正しいですか？

Answer 1

ソート済み（）がforループ内で使用されているので、コード全体の最悪の時間複雑さはO（n^2 log（n））です。

必ずしもそうである必要はありません。 forループはO（N）であり、sortedはO（N log N）ですが、これらの式の「N」は異なる値を参照しています。 O（N）中のNは、wordsの長さを指し、O（N log N）中のNは、wordの長さを指す。

各word文字列の平均長さがwordsリストの長さと等しい場合、アルゴリズムの複雑さはO（N^2 log N）であると言うことが正しいでしょう。たとえば、wordsに5つの単語が含まれていて、それぞれ5つの文字が含まれているとします。しかし、これはそうではありません。より一般的な結論は、アルゴリズムがO（m * n log n）であり、mがwordsのサイズに対応し、nが単語の平均サイズに対応することである。

Answer 2

ここでの漸近分析は、あなたが書いたように、実際には3つの入力の関数であるからです。すなわち、干し草、干し草の各単語の長さ、および針です。

ニードルのソートされた値をキャッシュすることができます。これらは静的です（この操作は干し草の反復によって圧倒されます）。

また、フィルタを使用するようにコードを簡略化しました。これはループの繰り返しを抽象化します。これはアルゴリズムのパフォーマンスに理論的な影響はありませんが、イテレータを返すと怠惰な結果が得られ、実際のパフォーマンスが向上する可能性があります。

周波数は整数なので、周波数の数に関してはO(n)でソートできます。

このように、干し草の中のすべての要素について、針の頻度と並べ替えて比較します。これはO(n*m)になります。ここで、nはhaystackのサイズで、mはhaystackの各要素のサイズです。

したがって、あなたのコードを簡略化することができます。

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

>>> def find_same_frequency_distribution(haystack, needle): 
...  needle_counts = sorted(Counter(needle).values()) 
...  return filter(lambda x: sorted(Counter(x).values()) == needle_counts, haystack) 
... 
>>> li = ["daddy", "mummy", "dddya", "foosa"] 
>>> for e in find_same_frequency_distribution(li, "babdb"): 
...  print(e) 
... 
daddy 
mummy 
dddya