Welcome To Ask or Share your Answers For Others

如何理解常数级别的额外空间？

asked Jan 24, 2021 in Technique[技术] by 深蓝 (71.8m points)

刚才刷算法题有个要求常数级别的额外空间，请问一下这句话该怎么理解?

与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…

3.7k views

Welcome To Ask or Share your Answers For Others

1 Answer

answered Jan 24, 2021 by 深蓝 (71.8m points)

如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)
当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)
当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)

以此类推

题中要求的 常数级别的额外空间 就是O(1)

与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…

...