algorithm - 给定 O(n) 集合，找出其中不同的集合的复杂性是多少？

Question

我有一个应用程序，其中有一个 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) 之外，还有其他方法可以在更短的最坏情况下运行时间吗？

Answer 1

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