1

我有一个问题，我需要将一组（唯一子集）中的唯一组合与给定值相关联。例如： Let S={a, b, c, d}，所需的数据结构应执行以下操作：

键 -> 值

{a,b} -> value1
{a,c} -> value2
{c,d} -> value3
  • 属性 1：密钥中集合的长度是固定的（在本例中固定为 2）。
  • 属性 2：数据结构不包含 S 的所有可能子集。

问题 1：保存这些值的简单 Map 的存储复杂度是多少？上！）？（假设 |S| = N 并且它不是固定的）

问题 2：是否有任何有效的数据结构可以存储这些元素？（存储复杂性需要最重要的效率）

4

1 回答 1

0

在一组 n 个项目中大小为 k 的不同子集的数量是n!/(k!*(nk)!)。这也将是存储值的映射的最佳存储复杂度。

您可以使用二叉树森林来表示子集。节点将包含一个键和两个子指针。叶节点将表示大小为 1 的子集。叶节点上方级别的父节点将表示大小为 3 的子集，因为它们包含一个键并指向两个包含键的叶节点。下一级父节点将代表大小为 7 的子集，依此类推。

你会得到一个有 n!/(k!*(nk)!) 个可能的根节点的森林。您的“简单映射”将是从根节点映射到存储值的哈希映射。

为了获得最佳的存储复杂性，您需要避免等效节点的重复。当你在你的林中创建一个节点时，你必须检查你是否已经创建了一个代表相同子集的节点。如果存在等效节点，则必须重用该节点而不是创建新节点。因此一个节点可以有很多父节点。（您可能希望将节点放在哈希表中以避免重复。）由于所述复杂性，森林将由顶级节点控制。由于每个节点的大小是固定的，整个森林的存储成本将由根节点的数量乘以一个常数来确定。

于 2013-09-08T19:54:16.807 回答