Python中index/rindex循环调用的时间复杂度及代码效率疑问

一、时间复杂度判定 #

先看你提到的第一段代码：

for c in s:
    if s.index(c) == s.rindex(c):
        return c

这段代码的最坏时间复杂度确实是O(n²)，原因如下：

• str.index(c)和str.rindex(c)的底层实现都是线性遍历字符串：index从左到右找第一个匹配的c，rindex从右到左找最后一个匹配的c，单个调用的时间复杂度都是O(n)。
• 最坏场景下（比如字符串前n-1个字符全重复，最后一个字符才是唯一的），循环会执行n次，每次调用两个O(n)的方法，总时间开销为O(n) * O(n) = O(n²)。

关于你看到的CPython源码里的嵌套while循环：那是处理Unicode字符多字节编码的细节，本质还是对字符串的线性遍历，并非针对整个字符串的嵌套遍历，所以单个index/rindex的时间复杂度依然是O(n)，不是O(n²)。

二、为何第一段代码实际测试更高效？ #

虽然理论复杂度更高，但在你的测试场景下它表现更好，核心原因有三点：

• 提前终止机制：如果字符串的前半部分甚至开头就存在唯一字符，第一段代码会立刻返回结果，不需要遍历完整字符串。比如10万长度的字符串，若第5个字符就是唯一的，这段代码只需要执行5次index/rindex调用，而字典统计代码必须先完整遍历10万字符完成计数，再遍历字典找结果，总遍历次数更多。
• C实现的性能优势：index和rindex是CPython用原生C实现的内置函数，执行速度远快于Python层面的字典操作（比如dict.get()、键值赋值都是Python字节码指令，单步开销比C代码大很多）。哪怕是几次O(n)的C操作，也可能比一轮完整的Python字典统计更快。
• 字典的额外开销：字典需要处理哈希计算、哈希冲突、内存分配与管理等额外逻辑，这些都会增加运行时间；而index/rindex直接操作字符串的底层内存，没有这些额外开销。

当然，这种优势只存在于存在早出现的唯一字符的场景。如果是最坏场景（唯一字符在末尾），字典统计的O(n)时间复杂度会碾压第一段代码的O(n²)表现。

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