算法 - 用于计算成对相互出现的次数

Question

我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值，那么我会得到一个列表 L2。我有另一个列表 L3，它是 L2 的某个子集。

我想找出 L1 中 L3 的元素成对相互出现的情况。关系是无向的。即 a,b 与 b,a 相同

例如- L1= [[a b c d][a b d g f][c d g][d g]...] L2=[a b c d g f] 说 L3 = [c d g]

我想在 L1 中找到 L3 的成对相互出现。即这些值。 三，二:2 d,g:3 c,g:1

我得到 O(n*n*m*p);哪里- p- 没有。 L1 中的列表，m - 平均。不。 L1 的每个列表中的元素。 n - 没有。 L3 中的元素。

我能否提高复杂度？

上面的python代码是:

这里sig_tags是L3，tags是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|)，具体取决于您如何实现它。

现在要检查一对是否属于列表，您需要检查某些 2 位是否为真，即 O(1)。所以所有的检查都将是 O(n^2*p)。

总体复杂度为 O(n^2*p + m*p)。

如果您使用哈希函数，则可以跳过分配 ID。小心，有时哈希函数计算很昂贵。