空间复杂度

来源：2-2 对数据规模有一个概念

诺巴蒂

2020-06-27

像原地交换这样的排序，空间复杂度认为是 O(1) 的,但比如 js 没有数组元素交换的函数，我自己写了一个，是不是每交换一次，都开辟了一个新的 tmp，这样空间复杂度是不是就变成了 O(n)

写回答

1回答

liuyubobobo

2020-06-28

已采纳

不是，还是 O(1)。

因为这一个 tmp，在交换以后，空间就回收了，下次再交换，还是用 1 的空间就够了。我们不需要用 n 的空间完成交换。

你也可以理解成，如果我们创建一个全局的 tmp 的话，只要一个空间，在所有的交换中都能用这个 tmp，就能完成全部交换。

继续加油！：）

追风筝的人or

太棒了

2020-09-01

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1