Python中map(int, str)时间复杂度探究及CSES问题超时分析

一、map(int, iterable)的时间复杂度本质 #

map函数本身只是轻量的迭代器包装器，它的时间复杂度完全由传入的映射函数（这里是int()）和迭代对象的规模决定，自身的额外开销可以忽略。真正影响性能的是字符串转整数的int()操作。

二、十进制字符串转int()的时间复杂度 #

你提到的O(N²)复杂度是旧版Python实现的历史问题——早期十进制转整数的算法存在低效的逐位累加逻辑，但在现代Python（3.10及以上版本）中，这个实现已经优化为O(N)线性时间，通过更高效的逐位解析和快速乘法完成转换。

不过即便如此，int()转换依然会产生额外开销：每个字符串数字需要遍历所有字符完成字符到数值的映射与累加，这一步的时间消耗是直接操作字符串时完全不需要的。

三、你的代码超时的核心原因 #

处理100000个数字时：

• 直接将拆分后的字符串存入集合，只需要对每个字符串做哈希计算（基于字符序列），没有额外转换步骤；
• 而先转整数再存集合，虽然整数的哈希计算更快，但前置的int()转换已经消耗了大量时间，整体开销远超直接操作字符串，最终导致超时。

四、map(int, 数字字符串列表)的总时间复杂度 #

假设共有k个数字字符串，每个字符串的平均长度为m：

• 现代Python中，总时间复杂度为O(k*m)，即线性于所有数字字符的总长度；
• 若使用未优化的旧版Python，总时间复杂度可能达到O(k*m²)，数据量大时极易超时。

内容的提问来源于stack exchange，提问作者Abhinav S.