jus*_*rld 6 algorithm variables big-o
我们有4种算法,所有这些算法都具有复杂性,具体取决于m和n:
Alg1:O(m+n)
Alg2:O(mlogm + nlogn)
Alg3:O(mlogn + nlogm)
Alg4 :( O(m+n!)哎哟,这个很烂,但无论如何)
现在,如果我们现在如何处理这个问题n>m呢？我的第一个想法是:大O符号"丢弃"常数和较小的变量,因为它无关紧要,但迟早"更大的术语"将压倒所有其他因素,使它们与计算成本无关.
那么,我们可以将Alg1重写为Alg1 O(n),还是将Alg2 重写为O(mlogm)？如果是这样,那么其他人呢？
是的,如果你知道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!)为了获得更精确的计算,你可以在这里看到这个线程两个复杂性O((2n + 1)!)和O(n!)是否相等？