Riy*_*lla 3 algorithm big-o subset subset-sum
是否有可能在O(n)时间和O(n)空间复杂度中找到所有可能的集合子集(即幂集) ？
程序设置 >> {a,b,c}
预计输入O(n)时间和O(n)空间复杂度,这里n为3.
{},{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}
不会.时间复杂度总是受限于输出的大小.由于一组大小为n的powerset的大小为2 n,因此不存在用于在小于O(2 n)内找到该powerset的算法.
就总空间而言,由于输出的大小为2 n,因此不能比O(2 n)更好.
虽然在术语辅助空间,给定一组小号尺寸的Ñ的幂的任何元件可以通过长度的二进制串来表示Ñ.表示一个元素是否每个位置X的小号是在该组.
例如,给定集合{a, b, c},字符串101表示子集{a, c}.
特别是因为二进制字符串是整数的表示,所以您可以在集合上定义一些顺序并枚举其元素.这需要作为中间存储,只有一个整数,其大小不超过O(n).
这在实现生成器的语言中特别有用,如果powerset几乎没有辅助存储,则可以遍历所有元素.