如果对两个数组进行排序，然后执行一个线性步骤来记录公共元素，则可以找到两个数组的交集。
这需要O（nlogn）+O（nlogn）+O（n）
或者，您可以将第一个数组中的每个元素与第二个数组中的每个元素进行比较，得到O（n ^ 2）运行时复杂度。
我如何证明第一种方法比第二种方法好？
最佳答案
首先，O(nlogn) + O(nlogn) + O(n)没有多大意义，因为O(f)是一个集合，而不是一个数字。
您的意思是O(nlogn + nlogn + n)，可以显示为等于O(nlogn)。看看函数f属于集合O(g)意味着什么：f是O(g) iFF的元素，存在c>0和x0，对于所有x>x0：|f(x)| <= c*|g(x)|
通过设置f=nlogn和g=nlogn+nlogn+n，可以看出f位于O(g)中，因此O(nlogn) == O(nlogn + nlogn + n)。
关于algorithm - 算法复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5795481/