Nlog(logN),NlogN,Nlog(N ^ 2)的运行时间是否相等？

Question

我认为NlogN和Nlog(N ^ 2)是等价的,并且Nlog(logN)具有比NlogN和Nlog(N ^ 2)更好的RT.谁能确认一下？

Answer 1

N*log(N^2) = 2N*log(N)

2N*log(N)相当于N*log(N)(当涉及大O表示法时,常量被跳过).NLog(logN)增长较慢(具有更好的运行时性能以增长N).

Answer 2

不.大O符号与实际运行时间无关.对于给定n值,O(n)可以比O(1)短,具体取决于实际实现.

Big O表示法是关于比较算法如何扩展的.意思是n增加,它们相对于彼此变化多少.

那么,一个例子:

function add100(x) {
    for (i = 0; i < 100; i++) {
        x++;
    }
    return x;
}

function twice(x) {
    tmp = x;
    for (i = 0; i < tmp; i++) {
        x++;
    }
    return x;
}

我知道,这些功能可以降低到x+100与2 * x分别,但出于演示的目的,他们很简单,显示我们希望他们.(有些编译器实际上可能会对它们进行优化,因此根据您的环境可能没有差别).

现在,add100(x)有一个算法的复杂性O(1).并且double(x)具有复杂性O(n).但是,对于x<100的值,twice(x)将比快add100(x).对于任意输入,它不会.它也不会扩展,但对某些输入范围来说速度更快.现在,这是一个简单的实现,并不是所有算法都有更快的输入范围,但它确实证明了O()符号对实际运行时没有影响......

但是,在这种特殊情况下,它是简单的对数数学.所以Log(m^n) == n * Log(m),因此n log(n) == log(n^n).所以n log(n) != n log(n^2)...但是,由于常量会以大O表示法删除,因此n log (n^2)会转换为2n log (n)变换为n log (n)...所以n log(n) == n log(n^2) 出于Big O表示法的目的 ......