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

Question

我要实现一种算法，我在纸上的想法与教科书中建议的伪代码略有不同。我试图说服自己，当必须分别在下面的两个和一个中实现所有子集的“包含”和生成时，下面伪的 2 个片段将做同样的事情，而时间复杂度的顺序没有任何重大差异。我很难想出能让我信服的严谨的东西。

T 和 A 是有限集 I 的子集集。没有集合或子集是空的，每个集合都有一个名为“计数”的“字段”。

片段一:

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 中当且仅当 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 中的所有 a，a.count 初始设置为 0)