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

Question

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

以下操作的 Big O 是什么？

据我了解，sortJS中嵌入函数的Big O是O(Nlog(N))，并且Big Omap是O(N)，因此Big O是O(Nlog(N))？

Answer 1

函数的复杂性f、arr大小n。我们假设：

\n

arr.sort \xe2\x88\x88 O(nlogn)\narr.map \xe2\x88\x88 O(n),\n

\n

我们可以对这些项求和，因为这些操作是串行完成的（一个接一个）。因此，

\n

f(n) \xe2\x88\x88 O(nlogn + n)\n

\n

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

\n

as n -> infinity, nlogn >> n\nthus, as n -> infinity, nlogn + n -> nlogn\n

\n

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

\n

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

\n