O(n) + O(n log n) 是否等于 O(n log n)？

Question

我完成的一段代码遵循以下结构：

for (i = 0; i < N; i++){ // O(N)
    //do some processing...
}

sort(array, array + N); // O(N log N)

大O符号中表示什么是复杂度？

提前致谢。

- Victor Nascimento

---

是的，n log n 的增长比 n 更强，因此它支配了整体增长。 - nhahtdh

如果你回顾一下大O符号的定义，你就能够自己回答这个问题了。如果你回顾后仍然困惑，那么我们可以指引你正确的方向。 - Dennis Meng

Answer 1

据我所知，big-O是用来描述算法渐近复杂度的。

O(x+y) = O(max(x,y))

因此，

O(n + n log n) = O(n log n)

- Kendall Frey

---

只是为了明确起见，O符号并不告诉你某个东西的绝对速度有多快，只是告诉你当n变得非常非常大时可以期望什么。 - Mark Ransom

大O求和规则的证明：https://dev59.com/KXLYa4cB1Zd3GeqPY4qI#16750079 - Imre Kerr

那么对于使用邻接表的常规深度优先搜索算法，时间复杂度为O(v+E)，是否等于O(E)？ - Ayyappa Gollu