algorithm - 当已知一个变量小于另一个变量时如何处理大 O？

Question

我们有 4 种算法，它们的复杂度都取决于 m 和 n，例如:

算法 1:O(m+n)算法 2:O(mlogm + nlogn)算法 3:O(mlogn + nlogm)Alg4:O(m+n!)(哎哟，这个很烂，但不管怎样)

现在，如果我们现在是 n>m，我们该如何处理呢？我的第一个想法是:大 O 表示法“丢弃”常量和较小的变量，因为这无关紧要，但“较大项”迟早会压倒所有其他项，使它们与计算成本无关。

那么，我们能否将 Alg1 重写为 O(n)，或将 Alg2 重写为 O(mlogm)？如果是这样，其他人呢？

Answer 1

是的，如果你知道 n>m 总是这样的话，你可以重写它。正式地，看看这个

如果我们知道 n>m(总是)那么它就是

O(m+n) < O(n+n)这是 O(2n) = O(n) (我们并不真正关心 2)

我们也可以对其他算法说同样的话

O(mlogm + nlogn) < O(nlogn + nlogn) = O(2nlogn) = O(nlogn)

我想您可以看到其他人的去向。但是如果你不知道 n > m 那么你就不能说上面的话。

编辑:正如@rici 很好地指出的那样，您还需要小心，因为它始终取决于给定的功能。 (注意 O((2n)!) 不能简化为 O(n!) )

稍加尝试就可以看出这不是真的

(2n)! = (2n) * (2n-1) * (2n-2)... < 2(n) * 2(n-1) * 2(n-2) ...

=> (2n)! = (2n) * (2n-1) * (2n-2)... < 2^n * n! (合并所有 2 个系数后)

因此我们可以看到O((2n)!)更像是O(2^n * n!)要获得更准确的计算，您可以在此处查看此线程 Are the two complexities O((2n + 1)!) and O(n!) equal?