大O符号——O(nlog(n))与O(log(n^2))

Question

NLog(N)和Log(N^2)的表示方式相同吗？如果是，为什么不这样写呢？

NLog(N)是标准表示法吗？我觉得Log(N^2)更容易理解。

- Nawlidge

---

"Log (x^2)" 在数学上是 "2 logx"，并且您需要消去常数。而 "n log n" 显然与此不同。 - zerkms

你为什么认为这些函数是相同的？即使你无法代数地操作它们，绘制这些函数将立即显示它们的不同之处。https://www.wolframalpha.com/input/?i=y%3Dx+log+x,+y%3Dlog(x%5E2),+x%3D1+to+1000 - Paul Hankin

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)) 要大得多。

下面这张图显示了它们之间的差异：

- Aziz

Answer 2

添加对数等同于乘法，因此log(n*n)变成了log(n)+log(n)=2log(n)。

n log(n)接近于线性增长。n是重要的部分，因为其余部分增长得相当缓慢。

例如，归并排序具有n log n的时间复杂度，因为如果将合并视为一棵树，则该树的高度为log(n)，每个级别上都会处理所有n个元素。

- Joonazan

---

这是否意味着 Nlog(N) = 2log(N)？ - Nawlidge

@Nawlidge No. log(N^2) = 2log(N)，而O(2log(N)) = O(log(N))。Nlog(N)则完全不同。例如，log10(100) = 2，但是100*log10(100)等于200。 - Joonazan

Answer 3

Nlog(N) = log(N^N)，正如zerkms所指出的那样，log(N^2) = 2log(N)

- FireFistAce