一种具有O(mlogn)复杂度的算法

Question

我正努力为这个问题找到确切的解决办法。

一所大学有两个学生俱乐部。注册到第一个俱乐部的学生数量是m，他们的is存储在数组A中(带有m个元素)，而注册到第二个俱乐部的学生数量是n，他们的is存储在数组B(包含n个元素)中，其中m≤n。学生可以注册到这些俱乐部中的任何一个，或者两者都注册。我们想决定有多少学生在这两个俱乐部注册。给定两个数组A和B以及它们的长度m和n，编写一个O(mlogn)算法(作为伪码)来查找两个俱乐部注册的元素数。例如，当A为2、6、3、9、11、8和B为3、11、7、4、2、5、1时，算法必须返回对应于in为2、3和11的学生的3。请详细解释为什么您的运行时间是O(mlogn)。

我想到的第一件事是对数组B进行排序，然后从A.排序O(nlogn)中搜索B中的每个元素，然后查找匹配的O(mlogn)，然后将结果变为O((m+n)logn)。

我想到的第二种方法是合并数组，然后查找复制的，但是是idk。

Answer 1

这个问题出了点问题。

如果B开始排序，就有一个O(m log(n))算法。

如果两者都没有排序，则有一个O(n log(m))算法。

但是，如果两者都没有排序，您甚至不能搜索B一次而不占用时间O(n)。O(m log(n))需要运行得更快，在m到无穷大的极限中，而n = m^2则是无限的。