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

Question

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

O(n log m) 对比 O(n + m)

分析这两种算法，哪一种更适合大规模使用？

例如）如果 n 和 m 呈指数级大，则变为

O(2e) 对比 O(e*(something linear to e))

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

1) 2 指针方法

2) 使用二分查找

Answer 1

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

1. “双指针”方法，即 O(m + n)。
2. 使用二分查找来确定数组 N 中的项是否在数组 M 中。这是 O(n log 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 log n)。这里，m=1000000，和log(n)=7（大约）

如果你在 M 中寻找 N，那么复杂度是 O(n log m)。n=100和log(m)=20（大约）。

在那种情况下你想要做什么很清楚。

在实践中，是否应该使用 O(m+n) 或 O(n log m)（其中 n 小于 m）算法之间的界限只能凭经验确定。这不仅仅是确定 是否 的问题(m + n) < (n log m)，因为二分搜索涉及一些双指针方法没有的开销。即使(m + n)是 double 或 three ，双指针方法也很可能会更快(n log m)。

Answer 2

无论是明确地更好，因为它依赖于相对价值n和m。

如果您假设它们相等，则您有O(n log n)vs O(n)，因此第二个 ( O(n + m)) 更快。另一方面，如果在快速增长的n同时有效地保持不变m，那么您正在查看O(log m)vs O(m)，因此第一个更好。

基本上，第一个更适合 large m，第二个更适合它们都很大的情况。（如果n在方程中占主导地位，那么它们都只是线性的。）