将字符串转换为其等效数字或反之亦然的复杂性是多少？它会根据编程语言而改变吗？
从表面上看，需要遍历整个字符串才能将其转换为数字，所以它是O(n)，还是使用了某种类型转换？
当我编写一个例程来检查给定的数字是否是回文时，这个疑问就出现了。一种方法是继续将数字除以基数（此处为 10），累积数字，然后将它们放在最后。示例：309/10=rem(9)、30/10=rem(0)、3/10=rem(3)。我们得到 903。
我采用的另一种方法是将这个数字转换为字符串，并且由于字符串有大量的成员函数可以拆分、反转等，因此代码更短更简洁，但这是最好的方法吗？
数字字符串是以位置表示法格式化的数字 - 因此需要考虑每个数字的值乘以基数的幂，以便将数字转换为二进制格式。
所以是的，这是一个 O(N) 操作，因为运行时间随着更多数字的添加而线性增加。然而，在实践中，N 可能会受到该语言支持的任何数字数据类型（例如 int32_t、int64_t）的限制。但是，如果使用任意精度的数字类型（某些语言，如 Python，默认使用），那么位数没有限制（显然可用内存除外）。
要转换为数字，您始终必须读取所有数字。所以至少是O(n)。
现在做类似（伪代码）的事情
a = 0
foreach digit in string
do
a = 10 * a + digit
end
是O(n)。所以复杂度是O(n)
C# 和 C/C++ 在表示（可能的）数值的字符串中没有任何特殊信息。因此，他们需要在转换时逐位解析字符串。
但是，位数是有限的，所以我们只有 O(1)：转换时间是有界的（通常是最大数字的转换）。对于 32 位 int，转换必须考虑最多 10 个十进制数字（可能还有一个符号）。
从字符串转换实际上也是 O(1)，因为在解析它的过程中，只考虑有限数量的字符（在 32 位 int 的情况下为 10+1）就足够了。
严格来说，我们不能O在 int 到字符串转换的情况下使用 -notation，因为 int 的最大值是有界的。无论如何，转换所需的时间（在两个方向上）都受到一个常数的限制。
正如@Charles 建议的那样，其他语言（Python）实际上可以使用任意精度的数字。对于解析这样的数字，时间分别是O(number of digits)、 whichO(string length)和O(log(number))对于这两种转换。对于任意精度的数字，不能更快地做到这一点，因为对于这两种转换都必须考虑每个数字。对于有限精度数的转换，同样的O(1)推理也适用。但是我自己并没有分析 Python 中的解析，所以可能在那里使用了效率较低的算法。
编辑：根据@Steve 的建议，我检查了 C/C++ 和 C# 中的解析是否跳过了初始空格，因此 string->int 转换的时间实际上是O(input length). 如果已知字符串已被修剪，则转换再次为O(1).
我有理由确定，如果编码正确，处理纯数字运算符（在 c++ 和 c# 中，我认为这将是“%”模运算符）会更有效，因为在某种程度上你必须检查类似的特性（确实结尾匹配开头）并且执行字符串和数字之间的转换只会增加操作的复杂性，如果您可以在不执行该转换的情况下执行相同的操作。
也就是说，我不会担心在数字和字符串之间转换对性能的影响，因为与程序的大多数其他区域的性能影响相比，它可能微不足道。数字类型限制为 64 位，这对您可以计划解析的位数设置了相对较低的上限，除非您正在实现/使用自定义编码的大数类型。
您不必担心复杂性是 O(n)，其中 n 是数字的大小。它更像是 O(n)，其中 n 是位数（我提到的低上限）或（如另一个回复中提到的）O(log(n)) 如果 n 是数字的大小。性能影响相对微不足道。
现在，如果按照您的建议，您对 N 没有限制（这是不可能的，因为使用 2 GB 的 RAM，您只能存储多达 20 亿位的数字），那么我们可能需要更多地考虑执行数学运算的性能运营商。考虑“%”和“/”运算符在这种大数类型上的性能。但随后意识到，为了将数字转换为字符串，无论如何它基本上都使用相同的运算符。再一次，如果你做得对，你不能直接把它当作一个数字来处理。
如果要将数字 N 转换为字符串。它需要以 10 为底的 O(log(N))。（如果除以 10 并保留余数）如果要转换长度为 N 的字符串，则需要 O(N)。（如果您使用不断添加到您的数字 10^(N)*digit(N) 的算法）
如果您使用不属于您的函数（比如说字符串），您只能期望它们会变慢。