algorithm - 计算一组矩阵上 for 循环的复杂性

Question

当我在 R 中对交互式网络建模时，我遇到了以下问题:

S 是像 A 这样的所有 (n x n) 方阵的集合:

• A的主对角线上的所有值都为0。
• 所有其他值(即 Aijs 使得 i 不等于 j)为 0 或 1。
• 如果 Aij = 1，则 Aji = 0。(但是，如果 Aij = 0，Aji 可能或者可能不是 0)

什么是S的基数？

我将编写一个程序来遍历所有此类矩阵(S 的所有成员)以检查某些属性。我知道复杂度是指数级的，但是，我只想检查一些小型网络。因此，我想了解 S 的基数随着 n 的增长而增长的一些小数。理想情况下，我正在寻找一个获取 n 并返回 S 的基数的函数。谢谢!

Answer 1

S 的基数是 3^(N(N-1)/2) 因为每对可以有三个状态 (00,01,10), 对数为矩阵(NxN)中的项数减去对角线上的项数(N )，除以 2(每对 2 个条目)。