O(n log m)和O(n+m)哪个更好？（涉及IT技术）

Question

11

嗨，这两个时间复杂度哪个更好。

O(n log m)和O(n + m)哪一个更适合在大规模使用时分析这两种算法？

例如) 如果 n 和 m 指数级增长，则变为

O(2e)与O(e*(something linear to e))

示例问题：2个数组中的公共元素：

1）双指针法

2）使用二分查找

- Dexters

3个回答

14

既然取决于n和m的相对值，因此两者都没有明确的优劣之分。

如果假设它们相等，那么你会得到O(n log n)与O(n)的比较，所以第二个（O(n + m)）更快。另一方面，如果n基本上是常数而m快速增长，那么你将面临O(log m)与O(m)的比较，这时第一个更好。

基本上，第一个适用于大的m，而第二个适用于它们都同样大的情况。（如果n主导方程式，那么它们都是线性的。）

- Edward Peters

1

总之，这取决于您选择的两个数组的长度，是m + n的值与（mlogn或nlogm中的一个）相对比。虽然大O复杂度分析不考虑对数的“底”，但对于这样的问题，其中值决定更好的复杂度，需要注意的一点是对数的“底”为“2”而不是“10”，在计算查看的元素数量或比较次数时需要采用特定的示例。

- Prashant G

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Mischel · Accepted Answer

我认为你在问如何找到两个已排序数组中的共同元素。你可以选择以下两种算法:

如果两个数组的大小相近，那么第一种方法比较适合，因为它严格线性。

如果其中一个数组比另一个数组大得多，那么你可能需要考虑二分查找的方法。你将要在较大的数组中搜索出现在较小数组中的项目。例如，如果你有数组M和N，其中M有100万项，而N只有100项，则你有以下选择：

如果你查找M在N中，则时间复杂度为O(m log n)。在这里，m=1000000，而log(n)=7（约）。

如果你查找N在M中，则时间复杂度为O(n log m)。在这里，n=100，而log(m)=20（约）。

在实践中，应该使用哪种算法（当n小于m时）的临界值只能通过经验确定。这不仅仅是计算是否 (m + n) < (n log m)，因为二分查找涉及一些开销，而双指针方法则没有。即使在 (m + n) 倍于 (n log m) 的情况下，双指针方法很可能仍然更快。