伪代码的两个简单部分的等价

Question

我将实现一种算法，其中我在纸上认为出来的方式与我们教科书中建议的伪代码略有不同。我试图说服自己，当下面的两个和一个分别实现“包含”和所有子集的生成时，下面的伪代码的两个片段将按照时间复杂度的顺序执行相同的操作。我很难提出一些能说服我的严格的事情。

T和A是有限集合I的子集的集合。没有集合或子集是空的，并且每个集合都有一个称为“count”的“字段”。

片段一：

For-each t in T do { 
    A_t = A intersected with the set of all non-empty subsets of t 
    For-each a in A_t do { 
    a.count++ 
    } 
} 

片段二：

For-each a in A do { 
    a.count = count(a, T) 
} 

这里计数由

count(a, T) { 
    c = 0 
    For-each t in T do { 
    if (t contains a) { 
     c++ 
    } 
return c 
} 

Answer 1

定义这取决于你如何实现你的子一代和包含的功能。我的猜测是，在大多数情况下，产生所有这些子集是不值得的，并（如a是A_t IFF a为A，并在一套t子集，即a是A_t IFF a为A和t包含a）你可以重写你的第一个片段到

For-each t in T do { 
    For-each a in A do { 
    if (t contains a){ 
     a.count++ 
    } 
    } 
} 

，而你的第二个片段是

For-each a in A do { 
    For-each t in T do { 
    if (t contains a){ 
     a.count++ 
    } 
    } 
} 

（在这两种情况下，假设对于所有a in A,a.count最初设置为0）