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）

这完全取决于函数的增长速度-仔细考虑它，然后您会明白为什么您可以忽略增长缓慢的函数。