给定 O(n) 集合，找出其中不同的集合的复杂性是多少？
Given O(n) sets, what is complexity of figuring out distinct ones amongst them?
我有一个应用程序，其中有 O(n) 个集合的列表。
每组 Set(i) 是一个 n-vector。假设 n=4，例如
Set(1) 可以是 [0|1|1|0]
Set(2) 可以是 [1|1|1|0]
Set(3) 可以是 [1|1|0|0]
Set(4) 可以是 [1|1|1|0]
我想处理这些集合，以便作为输出，我只得到其中唯一的集合。所以，在上面的例子中，我会得到输出：
Set(1), Set(2), Set(3)。请注意 Set(4) 被丢弃，因为它与 Set(2).
相同
计算这个的一种相当蛮力的方法给了我一个最坏情况的界限 O(n^3):
Given: Input List of size O(n)
Output List L = Set(1)
for(j = 2 to Length of Input List){ // Loop Outer, check if Set(j) should be added to L
for(i = 1 to Length of L currently){ // Loop Inner
check if Set(i) is same as Set(j) //This step is O(n) since Set() has O(n) elements
if(they are same) exit inner loop
else
if( i is length of L currently) //so, Set(j) is unique thus far
Append Set(j) to L
}
}
n 没有先验界限：它可以任意大。这似乎排除了将二进制集映射为十进制的简单散列函数的使用。我可能是错的。
除了 O(n^3) 之外，还有什么其他方法可以在更好的最坏情况 运行 时间内完成吗？
您可以考虑使用平衡二叉树来实现您的集合。在这样的树中插入一个新节点的成本是 O(lgm)，其中 m 是树中元素的数量。重复项将被隐式清除，因为如果我们检测到这样的节点已经存在，那么它就不会被添加。
在您的示例中，lookup/insertion 操作的总数为 n*n，因为有 n 个集合，并且每个集合有 n 个值。因此，总时间可能会扩展为 O(n^2*lg(n^2))。这在一定程度上优于 O(n^3)。
首先，这些不是集合而是位串。
接下来，对于每个位串，您可以将其转换为数字并将该数字放入哈希集中（或者简单地存储原始位串，大多数哈希集实现都可以做到这一点）。之后，您的哈希集包含所有唯一项。 O(N) 次，O(N) space。如果需要保持字符串的原始顺序，则在第一个循环中检查每个字符串是否已经在哈希集中，如果不在，则将其输出并插入到哈希集中。
O(n) 个长度为 n 的序列构成大小为 O(n^2) 的输入。没有比这更好的复杂性了，因为您可能至少需要阅读所有输入。例如，所有序列可能都是相同的，但您必须全部阅读才能知道这一点。
可以在O(n) 时间内将长度为n 的二进制序列插入到trie 或radix 树中，同时检查它是否已经存在。这是所有序列在一起的 O(n^2)，因此简单地使用 trie 或基数树来查找重复项是最佳的。
参见：https://en.wikipedia.org/wiki/Trie
和：https://en.wikipedia.org/wiki/Radix_tree
如果你可以额外使用 O(n) space，你可以试试这个：
首先，我们假设向量是二进制数，所以 0110 变成 6。
- 这是为了防止向量中的数字是 [0,1]，否则你可以乘以 10 而不是 2。
将所有向量转换为小数需要 O(4n)。
对于每个转换后的数字，我们将通过十进制数映射向量。为了实现这一点，我们将使用 n-sized hash-map.
- HM <- n-sized hash-map
- 对于每个向量 v：
num <- v 转换后的十进制数
通过 num
将 v 映射到 HM
- 遍历 HM，每个索引只取一个
运行时步骤：
- O(n)
- O(n*(4+1)) ，其中1为映射时间，4为向量长度
- O(n)
我有一个应用程序，其中有 O(n) 个集合的列表。
每组 Set(i) 是一个 n-vector。假设 n=4，例如
Set(1) 可以是 [0|1|1|0]
Set(2) 可以是 [1|1|1|0]
Set(3) 可以是 [1|1|0|0]
Set(4) 可以是 [1|1|1|0]
我想处理这些集合，以便作为输出，我只得到其中唯一的集合。所以，在上面的例子中，我会得到输出：
Set(1), Set(2), Set(3)。请注意 Set(4) 被丢弃，因为它与 Set(2).
计算这个的一种相当蛮力的方法给了我一个最坏情况的界限 O(n^3):
Given: Input List of size O(n)
Output List L = Set(1)
for(j = 2 to Length of Input List){ // Loop Outer, check if Set(j) should be added to L
for(i = 1 to Length of L currently){ // Loop Inner
check if Set(i) is same as Set(j) //This step is O(n) since Set() has O(n) elements
if(they are same) exit inner loop
else
if( i is length of L currently) //so, Set(j) is unique thus far
Append Set(j) to L
}
}
n 没有先验界限：它可以任意大。这似乎排除了将二进制集映射为十进制的简单散列函数的使用。我可能是错的。
除了 O(n^3) 之外，还有什么其他方法可以在更好的最坏情况 运行 时间内完成吗？
您可以考虑使用平衡二叉树来实现您的集合。在这样的树中插入一个新节点的成本是 O(lgm)，其中 m 是树中元素的数量。重复项将被隐式清除，因为如果我们检测到这样的节点已经存在，那么它就不会被添加。
在您的示例中，lookup/insertion 操作的总数为 n*n，因为有 n 个集合，并且每个集合有 n 个值。因此，总时间可能会扩展为 O(n^2*lg(n^2))。这在一定程度上优于 O(n^3)。
首先，这些不是集合而是位串。
接下来，对于每个位串，您可以将其转换为数字并将该数字放入哈希集中（或者简单地存储原始位串，大多数哈希集实现都可以做到这一点）。之后，您的哈希集包含所有唯一项。 O(N) 次，O(N) space。如果需要保持字符串的原始顺序，则在第一个循环中检查每个字符串是否已经在哈希集中，如果不在，则将其输出并插入到哈希集中。
O(n) 个长度为 n 的序列构成大小为 O(n^2) 的输入。没有比这更好的复杂性了，因为您可能至少需要阅读所有输入。例如，所有序列可能都是相同的，但您必须全部阅读才能知道这一点。
可以在O(n) 时间内将长度为n 的二进制序列插入到trie 或radix 树中，同时检查它是否已经存在。这是所有序列在一起的 O(n^2)，因此简单地使用 trie 或基数树来查找重复项是最佳的。
参见：https://en.wikipedia.org/wiki/Trie 和：https://en.wikipedia.org/wiki/Radix_tree
如果你可以额外使用 O(n) space，你可以试试这个：
首先，我们假设向量是二进制数，所以 0110 变成 6。
- 这是为了防止向量中的数字是 [0,1]，否则你可以乘以 10 而不是 2。
将所有向量转换为小数需要 O(4n)。 对于每个转换后的数字，我们将通过十进制数映射向量。为了实现这一点，我们将使用 n-sized hash-map.
- HM <- n-sized hash-map
- 对于每个向量 v： num <- v 转换后的十进制数 通过 num 将 v 映射到 HM
- 遍历 HM，每个索引只取一个
运行时步骤：
- O(n)
- O(n*(4+1)) ，其中1为映射时间，4为向量长度
- O(n)