Python中使用isalnum()的循环语句时间复杂度计算咨询

你提到的认为代码时间复杂度为O(n²)的观点是错误的，错误原因是对str.isalnum()的调用场景存在误解，具体分析如下：

• 首先澄清char.isalnum()的时间复杂度：该方法的调用对象是长度为1的单个字符，其底层实现是直接查询Unicode字符属性映射表，属于固定开销的O(1)操作，和输入段落的总长度n没有任何关联。只有当你对长度为k的长字符串整体调用isalnum()时，时间复杂度才是O(k)，这一场景和当前代码完全不符。
• 其次分析循环整体的基础开销：遍历段落的n个字符是O(n)次数的迭代，每次迭代中的isalnum()判断、lower()转换（同样是单个字符的O(1)操作）都是常数开销，这部分整体是O(n)。
• 最后说明字符串拼接的潜在影响：Python的字符串属于不可变类型，在没有做特殊优化的旧版本/非主流Python实现中，每次执行normalized_str += ...都会生成新的字符串对象，需要复制当前已有字符串的所有字符，这种情况下拼接部分的总开销会达到O(n²)。但当前主流CPython实现已经对字符串的增量赋值操作做了预分配缓冲区的优化，平摊后拼接的开销也是O(1)每次，最终整体时间复杂度为O(n)。如果要兼容所有实现保证O(n)复杂度，可以改为用列表缓存结果最后join，优化后代码如下：

normalized_buf = []
for char in paragraph:
    if char.isalnum():
        normalized_buf.append(char.lower())
    else:
        normalized_buf.append(' ')
normalized_str = ''.join(normalized_buf)

内容的提问来源于stack exchange，提问作者Confucius