Big O表示法 - O(nlog(n))vs O(log(n ^ 2))

Question

NLog(N)的符号是否与Log(N ^ 2)相同？如果是这样,为什么不写那样？

NLog(N)是标准符号吗？我觉得Log(N ^ 2)不那么令人困惑.

Answer 1

• O(log(n^2))很简单O(2 log(n)) = O(log(n)).它是一个对数函数.它的值远小于线性函数O(n).

• O(n log(n))是一个更大的功能.它的值大于线性函数O(n)

它们是完全不同的功能(以及不同的大O复杂性).O(n log(n))远大于O(log(n^2))

该图显示了差异: