アルゴリズム - 対の相互発生をカウントするため

Question

私はリストのリストを持っています。 L1 = [[...] [.....] [.....] .....] リストを平坦化してからすべての要素を取り出し、そこから一意の値を抽出すると、リストL2が得られます。 私はL2のいくつかのサブセットである別のリストL3を持っています。

私は、L1のL3の要素のペアごとの相互出現を見出したいと思います。関係は無向である。すなわち、bが、

EG-L1 = Bと同じである[ABCD] [abdgf] [CDG] [DG] ....] L2 = [abcdgf] はL3 = [CDG]を言います

L1でL3のペアの賢明な相互出現を見つけたいと思います。すなわちこれらの値。 C、D：2 D、G：3 C、G：1

Iは、O（N×n個×m個* pを）取得しています。どこにでもあります。 L1、m - 平均のリストの数。いいえ。 L1の各リスト内の要素の数。 n - no。 L3の要素の

複雑性は改善できますか？上記Pythonで用

コードである：ここ

はsig_tags L3とタグがL1です。

x=[] 
    for i in range(len(sig_tags)): 
     for j in range(i+1,len(sig_tags)): 
      count=0 
      for k in tags: 
       if (sig_tags[i] in k) and (sig_tags[j] in k): 
        count+=1 
      if count>param:   
       x.append([sig_tags[i],sig_tags[j],count]) 
    return x 

Answer 1

はいできます。

各要素にidを与え、リストL1をビットベクトルのリストに変換します。リストが対応する文字を保持する場合は、ビットが真となります。これはO（m * p）、またはO（M * p * log | Alphabet |）です。

ペアがリストに属しているかどうかを確認するには、cerainの2ビットがO（1）であるかどうかを確認する必要があります。だから、すべての小切手はO（n^2 * p）になります。

全体的に複雑さはO（n^2 * p + m * p）です。

ハッシュ関数を使用する場合は、譲渡IDを省略することができます。ハッシュ関数の計算が高価な場合があることに注意してください。