algorithm - O(nlogn)+O(n)、O(nlogn) 和 O(nlogn + n) 之间的关系是什么？

Question

直觉上，我认为这三个表达式是等价的。

例如，如果一个算法在 O(nlogn) + O(n) 或 O(nlogn + n) 中运行(我很困惑)，我可以假设这是一个O(nlogn) 算法？

什么是真相？

Answer 1

是的，你可以说这是一个O(nlogn)。

当您尝试估计算法的复杂性时，您会从所有部分开始(选择每个部分中最差的操作并忽略快速的操作 - 嘿，这只是一个估计)。第一部分是 nlogn，第二部分是 n。

因为你不希望/不能/不需要它是准确的。

O(nlogn + n) - 或 - O(nlogn) + O(n) -> nlogn 增长速度比 O(n) 快，因此你可以忽略 O(n) -> O(nlogn)

一切都与函数增长的速度有关 - 把它想象成它很大，然后你就会明白为什么你可以忽略增长较慢的函数。

更准确的解释:http://en.wikipedia.org/wiki/Big_O_notation