我有一个应用程序,其中有一个 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]
我想处理这些集合,以便作为输出,我只得到其中唯一的集合。所以,在上面的例子中,我会得到输出:
设置 (1)、设置 (2)、设置 (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(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
关于algorithm - 给定 O(n) 集合,找出其中不同的集合的复杂性是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57050341/