database-design - 算法/数据库规模缩放分析

Question

我无法找到解释我的数据模型大小要求的公式。

我将有一个标签列表。在示例中，标签只是数字。
标签总是排序的，不存在重复的。

3 个数字的所有可能的标签组合：

1:2:3
1:2
1:3
2:3
1
2
3

4个数字：

1:2:3:4
1:2:3
1:2:4
1:3:4
2:3:4
1:2
1:3
1:4
2:3
2:4
3:4
1
2
3
4

我计算的一些值：

1=>1
2=>3
3=>7
4=>15
5=>29
6=>70

n 个标签最多有多少行（如上）？

Answer 1

这是一个组合问题：您想要选择“N 中的 1 项”+“N 中的 2 项”+“N 中的 3 项”+ ...最多“N 中的 N 项”的方式数之和。

N 中 N 的可能组合之和为 2^N，因此数据库中的行将为 2^N-1（因为空组合不是有效行）。

有关组合总和的详细说明，请参见这篇文章。

您也可以从集合的角度来考虑这一点——您想要一组 N 个项目的子集数（不包括空集）。