algorithm - 为什么字符串的空间复杂度是 O(n) 而数字是 O(1)？

Question

我对辅助空间复杂性有点迷茫。

在我参加的讲座中，讲师指出字符串具有 O(n) 的空间复杂度，因为字符串(n) 的长度会有所不同。但是诸如数字、布尔值、未定义等原语具有恒定的空间复杂度 O(1)。

我很困惑，因为如果字符串的空间因长度不同而不同，那么数字也会不一样吗？因为它们也会有不同的“长度”？

我确实理解布尔值和未定义是 O(1)，我的意思是真/假，未定义和 null 是与长度无关的实例。

如果有人能为我澄清这一点，我将不胜感激。

标签： algorithmspace-complexity

Answer 1

在现实世界中，数字大小确实是无限的，但这里是关于数字原语。根据定义，每个原语都需要固定数量的存储单元（这就是它只能保存有限范围值的原因）。与数字原语不同，字符串的大小在理论上是无限的，它占用与输入大小相对应的存储空间（即构成字符串的字符）。