能否以O(2^n)时间复杂度遍历输出所有长度为2^n的平衡比特向量

核心结论 #

对于任意给定的参数n，无法保证在O(2^{n)的时间复杂度下打印所有满足条件的2}n位平衡比特向量，仅当n=1时刚好符合该时间要求，n≥2时耗时会远超上限。

推导依据 #

• 首先计算符合要求的平衡比特向量总数量：长度为2^{n的比特向量中恰好有2}(n-1)个1的组合数为组合公式C(2^n, 2^(n-1))，表示从2^{n个位置中选2}(n-1)个位置放置1的所有可能性。
• 用斯特林公式近似计算该组合数的量级：C(2k,k) ≈ 4^k / sqrt(πk)，代入k=2^(n-1)可得：

  C(2^n, 2^(n-1)) ≈ 2^{2^n} / sqrt(π·2^{n-1})
  这个数值的增长速度远快于O(2^{n)：仅n=3时总数量就达到70，是2}3=8的8倍以上；n=4时总数量为12870，是2^4=16的800多倍，随着n增大二者的差距会呈指数级拉开。

• 哪怕忽略打印每个向量的字符耗时，仅遍历所有符合要求的向量的时间就已经远高于O(2^{n)的上限，更不用说每个向量本身长度就有2}n位，打印单个向量的时间都需要O(2^{n)，只要输出数量大于1，总耗时就会超过O(2}n)的要求。

补充说明 #

如果把时间复杂度要求放宽到O(总输出长度)，是存在对应生成算法的，比如经典的组合枚举递归算法，可以无重复地按序生成所有符合要求的比特向量。

内容的提问来源于stack exchange，提问作者sqrta deng