javascript - Javascript数组：什么是执行排序然后映射的大O？

Question

arr.sort((a, b) => a - b).map(num => num ** 2);

以下操作的大 O 是什么？

据我了解sort，JS 中嵌入函数的 Big O isO(Nlog(N))和 Big O mapis O(N)，因此 Big O is O(Nlog(N))？

标签： javascriptperformancesortingtime-complexitybig-o

Answer 1

您的功能的复杂性f，对于arr大小n。我们假设：

arr.sort ∈ O(nlogn)
arr.map ∈ O(n),

我们可以将这些项相加，因为这些操作是连续完成的（一个接一个。因此，

f(n) ∈ O(nlogn + n)

请注意，该nlogn术语将缓慢增长，但最终：

as n -> infinity, nlogn >> n
thus, as n -> infinity, nlogn + n -> nlogn

所以我们可以简化为刚好O(nlogn)足够大n。

所有这一切都是在说，是的，你明白了。