问O(n log ) vs O(n+m) -哪个更好？

EN

我认为您要问的是如何最好地找到两个排序数组中的公共元素。您可以选择两种算法：

1. “双指针”方法，即O(m + n)。
2. 使用二进制搜索来确定数组N中的项是否在数组M中，这是O(n日志m)。

如果阵列大小相近，那么第一个严格线性的算法更好。

如果其中一个数组比另一个数组大得多，那么您可能需要考虑二进制搜索方法。您需要在较大的数组中搜索较小数组中的项。例如，如果有数组M和N，其中M有1,000,000项，N有100项，则可以选择：

• 查找N中的M(即对100数组进行1,000,000次搜索)
• 查找M中的N(即对1,000,000数组进行100次搜索)

如果在N中查找M，则复杂度为O(m )。这里，m=1000000和log(n)=7 (大约)

如果在M中查找N，则复杂度为O(n log )。n=100和log(m)=20 (约)

在这种情况下你想做的事情很明显。

在实际应用中，使用O(m+n)还是O(n log )(其中n小于m)算法之间的界限只能通过经验来确定。这不仅仅是一个计算(m + n) < (n log m)的问题，因为二进制搜索涉及一些开销，而双指针方法并不是这样，即使(m + n)是双(n log m)还是三(n log m)，也很可能会更快。

这两种情况都没有明显的改善，因为这取决于n和m的相对值。

如果假设它们是相等的，那么就有O(n log n)和O(n)，所以第二个(O(n + m))更快。另一方面，如果n实际上是常数，而m增长很快，那么您将看到O(log m)与O(m)，所以第一个更好。

基本上，对于大型m来说，第一种更好，对于它们都很大的情况，第二种更好。(如果n控制方程，那么它们都是线性的。)

总之，它是m+n与( mlogn或nlogm之一)的值，这取决于您所选择的两个数组的长度。虽然大O复杂度分析没有考虑对数的“基数”，但对于这样的问题，在这些问题中，数值决定了更好的复杂性，但需要注意的一点是，对数的基数是"2“，而不是"10”，用具体的例子来计算所观察的元素数或所做的比较的数量。