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

Question

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

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 中，当且仅当 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）