时间/空间复杂性 - 如何弄清楚这个功能？

作者: v-star*위위
发布时间: 2024-04-09 08:17:52 (10天前)
转自：

3 条回复

0#
回复此人
AsuRa | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 是的，时间的复杂性是 <code> O(n^2) </code> - 例如，如果 <code> arr </code> 有10项，算法需要在完成前进行~100次比较。 </p> <P> 空间复杂性是 <code> O(n) </code> 。例如，考虑外部的最后一次迭代 <code> .filter </code> - <code> result </code> 这几乎完成了构建需要 <code> O(n) </code> 当时的空间（最坏情况;相当于输入的一侧） <code> arr </code> ）。回调内部的内部数组被过滤（然后将有它的 <code> length </code> 检查，并返回）也将是最糟糕的情况，输入的一面 <code> n </code> 。因此，目前在任何时间点使用的最大空间是 <code> O(2n) </code> ，相当于 <code> O(n) </code> 。 </p> </DIV>

编辑
1#
回复此人
12345 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 我认为你对时间复杂度是正确的，由于两个嵌套循环，它是O（n ^ 2）。 </p> <P> IMO空间复杂度为O（n），因为您只需要n个单位的空间来保留阵列，并且不会分配额外的内存。 </p> </DIV>

编辑

登录后才能参与评论