在打印两个数组中的公共(public)元素时，很难掌握大 O。一个尺寸为a，另一个尺寸为b。
我知道两个未排序的数组的复杂度是 O(ab)
但是当 a 未排序而 b 已排序时呢？
当两者都排序时？
任何解释都会很棒。
最佳答案
实现此目的的有效方法是使用哈希表(Java 中的HashMap)。一个算法是:
foreach element of the smallest array (1) O(N)
add element to the hash table (2) O(1)
foreach element of the biggest array (3) O(M)
if element is in the hash table (4) O(1)
print element
上面的伪代码中注释了每一步的时间复杂度。
- 迭代大小为 X 的数组的元素的时间复杂度为 O(X) 且内存复杂度恒定(元素的大小)
- 在哈希表中插入元素具有恒定的时间和空间复杂度
- 检查某个元素是否在哈希表中具有恒定的时间和空间复杂度
所以总体时间复杂度为O(N + M)，空间复杂度为O(N)
请注意
- 这种复杂性不受数组是否排序的影响
- 只有当最小的数组可以容纳在内存中时，此算法才有效
- 最好使用最小的数组构建哈希表，因为在内存中较小的哈希表会减少
希望有帮助!
关于java - 在已排序和未排序数组中查找公共(public)元素的 Big-O，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36522376/