algorithm- zum Zählen von paarweisen gegenseitigen Vorkommen

Question

Ich habe eine Liste von Listen. L1 = [[...] [...] [.....] .....] Wenn ich alle Elemente nach dem Reduzieren der Liste und Extrahieren von eindeutigen Werten nehme, dann erhalte ich eine Liste L2 . Ich habe eine andere Liste L3, die eine Teilmenge von L2 ist.

Ich mag das paarweise gegenseitige Vorkommen der Elemente der L3 in L1 zu finden. Die Beziehung ist nicht gerichtet. dh a, b ist gleich wie b, a

EG- L1 = [[abcd] [abdgf] [cdg] [dg] ....] L2 = [abcdgf] sagen L3 = [cdg]

Ich möchte paarweise gemeinsame Vorkommen von L3 in L1 finden. d.h. diese Werte. c, d: 2 d, g: 3 c, g: 1

Ich erhalte O (n * n * m * p); wo- Nr. von Listen in L1, m - avg. Nein. von Elementen in jeder Liste von L1. n - nein. von Elementen in L3.

Kann ich eine verbesserte Komplexität erhalten?

-Code für oben in Python ist:

Hier sig_tags ist L3 und Tags L1 ist.

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

Ja, Sie können.

jedes Element Geben Sie ein ID, wandeln dann die Liste L1 in eine Liste von Bit-Vektoren, in denen ein Bit wahr ist, wenn die Liste die entsprechenden Buchstaben constains. Dies ist O (m * p) oder O (M * p * log | Alphabet |), je nachdem, wie Sie es implementieren. wenn cerain 2 Bits

nun zu prüfen, ob ein Paar müssen Sie eine Liste gehört zu überprüfen, wahr sind, die O (1) ist. Also werden alle Überprüfungen O (n^2 * p) sein.

Insgesamt ist die Komplexität O (n^2 * p + m * p).

Sie können die Zuweisung von IDs überspringen, wenn Sie eine Hash-Funktion verwenden. Seien Sie vorsichtig, manchmal ist die Berechnung der Hash-Funktion teuer.