算法复杂度比较

Big-O notation 不会告诉你一个特定的算法对于一个特定的数据集有多快-它告诉你渐近性能。在Big-O表示法中,可以忽略常量和常量系数:

1. O(N+M*log(M))
2. O(N)

现在你可以看到第二种算法有更好的渐近性能。

在一般情况下比较复杂性时,忽略常量值。

O(N+1000 + M*log(M))

O(N + M*log(M))

虽然

O(N*5 + 2000)

变成

O(N)

现在,如果你确定这些是M和N的值,你可以做数学运算,更精确,但是你还必须知道每个运算需要多长时间——大O符号用于缩放,而不是算法在特定情况下的表现。如果您的数据是静态的,那么您最好运行这两种算法,看看哪种返回更快。

恰当地说, O(N+1000) + O(M*log(M)) 实际上没有任何意义,因为O(f(n))是所有函数g(n)的集合,所以诸如此类在大白书中查找诸如此类。。。安迪:你不能添加函数集。

是的,这是一种常见的滥用记谱法的行为,但是,由于迂腐,(而且已经教了那门课好几遍)我不得不指出正确的答案是“Mu”。

扩展一下:原因是Big-O符号被认为是渐近增长的标志,用外行的话说,这意味着描述算法复杂性的Big-O符号显示了对于一个非常大的输入大小,它会变得多快或多慢。这是因为“渐近”指的是“接近渐近线”(函数未定义的地方),在大O表示法的情况下,它指的是无穷大(例如,非常大的输入大小)。

现在,出于这个原因,我觉得非常奇怪,在大O中会有加法或常数乘法-你应该去掉那些用大O表示法的。。。这就是重点。这个问题就是这样问的吗?另外,算法不应该用 二