关于额外空间的问题
来源：1-2 Partition
慕粉4405724
2020-09-05 01:19:35
请问老师 使用swap的时候不是也使用了临时的额外空间吗？是因为量级太小所以可以忽略吗？与开两个数组空间相比的话 谢谢
写回答
1回答
-
liuyubobobo
2020-09-05
swap 只会开一个空间，1 是一个常数，在大 O 意义下，常数被忽略。
所以一个算法，如果需要一个额外的 n 的数组和一个常数空间用于交换，他需要的额外空间是 n + 1 的。O(n + 1) = O(n)。
继续加油！：）
0
相似问题