计算N组交叉点的快速算法

Question

我有n套A0,A2,...... An-1持有一套E的物品.

我将配置C定义为由n位组成的整数,因此C的值介于0和2 ^ n-1之间.现在,我定义以下内容:

(C)   an item e of E is in configuration C 
       <=> for each bit b of C, if b==1 then e is in Ab, else e is not in Ab

例如,对于n = 3,配置C = 011对应于在A0和A1中但不在A2中的E项(NOT是重要的)

C[bitmap]是在集合中具有完全存在/不存在模式的元素的数量. C[001]是A0中不在任何其他集合中的元素数量.

---

另一个可能的定义是:

(V)   an item e of E is in configuration V 
       <=> for each bit b of V, if b==1 then e is in Ab

例如,对于n = 3,(V)配置V = 011对应于A0和A1中的E项

V[bitmap]是所选集合的交集计数. (即位图为真的所有集合中有多少个元素的计数.) V[001]是A0中元素的数量. V[011]是A0 和 A1 中元素的数量,无论它们是否也在A2中.

---

在下文中,第一图片显示组A0,A1和A2的项目,第二图片显示(C)配置的大小,第三图片显示(V)配置的大小.

我也可以通过两个向量中的任何一个来表示配置:

C[001]= 5       V[001]=14
C[010]=10       V[010]=22
C[100]=11       V[100]=24
C[011]= 2       V[011]= 6
C[101]= 3       V[101]= 7
C[110]= 6       V[110]=10
C[111]= 4       V[111]= 4

我想要的是编写尽可能有效转化成c ^ V作为一个可能的C/C++函数.一个天真的方法可能是以下'transfo'函数,显然在O(4 ^ n):

#include <vector>
#include <cstdio>

using namespace std;

vector<size_t> transfo (const vector<size_t>& C)
{
    vector<size_t> V (C.size());

    for (size_t i=0; i<C.size(); i++)
    {
        V[i] = 0;

        for (size_t j=0; j<C.size(); j++)
        {
            if ((j&i)==i)  { V[i] += C[j]; }
        }
    }

    return V;
} 


int main()
{
    vector<size_t> C = { 
        /* 000 */  0,
        /* 001 */  5,
        /* 010 */ 10,
        /* 011 */  2,
        /* 100 */ 11,
        /* 101 */  3,
        /* 110 */  6,
        /* 111 */  4
    };

    vector<size_t> V = transfo (C);

    for (size_t i=1; i<V.size(); i++)  {  printf ("[%2ld]  C=%2ld   V=%2ld\n", i, C[i], V[i]);  }
}

我的问题是:对于将矢量C转换为矢量V,是否存在比天真更有效的算法？这种"好"算法的复杂性是什么？

请注意,我可能对任何SIMD解决方案感兴趣.

Answer 1

好吧,你正在尝试计算2 ^n个值,所以你不能做得比O(2 ⁿ)好.

天真的方法从观察开始,即通过固定X中的所有1位并迭代0位所有可能的值来获得V [X].例如,

V[010] = C[010] + C[011] + C[110] + C[111]

但是这种方法对V的每个元素执行O(2 ⁿ)个加法,产生O(4 ⁿ)的总复杂度.

这是一个O(n×2 ⁿ)算法.如果存在O(2 ⁿ)算法,我也很好奇.

我们n = 4.让我们考虑V对C的完整表.下表中的每一行对应于一个V值,该值通过对标记为a的列求和来计算*.*符号的布局可以从朴素的方法中轻松推导出来.

    |0000|0001|0010|0011|0100|0101|0110|0111||1000|1001|1010|1011|1100|1101|1110|1111
0000| *  | *  | *  | *  | *  | *  | *  | *  || *  | *  | *  | *  | *  | *  | *  | *  
0001|    | *  |    | *  |    | *  |    | *  ||    | *  |    | *  |    | *  |    | *  
0010|    |    | *  | *  |    |    | *  | *  ||    |    | *  | *  |    |    | *  | *  
0011|    |    |    | *  |    |    |    | *  ||    |    |    | *  |    |    |    | *  
0100|    |    |    |    | *  | *  | *  | *  ||    |    |    |    | *  | *  | *  | *  
0101|    |    |    |    |    | *  |    | *  ||    |    |    |    |    | *  |    | *  
0110|    |    |    |    |    |    | *  | *  ||    |    |    |    |    |    | *  | *  
0111|    |    |    |    |    |    |    | *  ||    |    |    |    |    |    |    | *  
-------------------------------------------------------------------------------------
1000|    |    |    |    |    |    |    |    || *  | *  | *  | *  | *  | *  | *  | *  
1001|    |    |    |    |    |    |    |    ||    | *  |    | *  |    | *  |    | *  
1010|    |    |    |    |    |    |    |    ||    |    | *  | *  |    |    | *  | *  
1011|    |    |    |    |    |    |    |    ||    |    |    | *  |    |    |    | *  
1100|    |    |    |    |    |    |    |    ||    |    |    |    | *  | *  | *  | *  
1101|    |    |    |    |    |    |    |    ||    |    |    |    |    | *  |    | *  
1110|    |    |    |    |    |    |    |    ||    |    |    |    |    |    | *  | *  
1111|    |    |    |    |    |    |    |    ||    |    |    |    |    |    |    | *  

请注意,左上角,右上角和右下角包含相同的布局.因此,我们可以批量执行一些计算,如下所示:

1. 计算表格的下半部分(右下角).
2. 将值添加到上半部分.
3. 计算左上角.

如果我们让q = 2 ⁿ,那么复现的复杂性就是

T(q)= 2T(q/2)+ O(q)

解决了使用主定理来

T(q)= O(q log q)

或者,就n而言,

T(n)= O(n×2 ⁿ)