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

Question

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

algorithmspace-complexity

6

我对辅助空间复杂度有些困惑。

在我上的讲座中，教师指出字符串的空间复杂度为O(n)，因为字符串的长度（n）会变化。但是像数字，布尔值，未定义等原始类型的空间复杂度为O(1)。

我感到困惑，因为如果字符串的空间复杂度因其长度而异，那么数字也不是同样吗？因为它们也将有不同的“长度”？

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

如果有人能为我澄清这个问题，我会很感激。

- ninja_nugget

1

如果你必须处理任意大的数字，那么存储整数N将占用O(log |N|)位空间，然后你还必须考虑对它们进行算术运算的时间复杂度（因为你不能在O(1)时间内加/减/乘/除任意大的数字）。为简单起见，通常假设所涉及的数字与问题的实际输入大小相比不是“太大”，但当输入只是一个单独的数字时，你必须更加小心。 - kaya3

1

一个字符串基本上是一个字符（或字节）数组，而一个数组的大小为O(n)，其中n是元素的数量。 - ChatterOne

2个回答

1

所有计算机使用的数字都有限制。例如，C的限制在此处。因此，如果您尝试分配超出此限制的数字，则程序会出错或开始表现奇怪。这意味着数字可以且通常以恒定数量的字节存储。

字符串没有这样的限制。除了内存，这很少是一个问题。

- Euphoric

我认为这是误解了重点；对于复杂度分析来说，通常从固定的有限限制推理是错误的，因为否则例如平方-乘算法需要O(1)时间，因为只有有限的可能输入。更微妙的例子是，冒泡排序的最坏情况时间是当数组像[5, 4, 3, 2, 1]时，但如果您的数字必须受到常数的限制，那么您无法构造出这样任意长度n的最坏情况。 - kaya3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SomeWittyUsername · Accepted Answer

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