Python3中字符串str.__getitem__方法的时间复杂度及实现原理咨询

工作原理 #

Python中的字符串属于不可变的序列类型，在CPython底层实现里，字符串是以连续内存块的形式存储Unicode码点的。当你使用下标（比如string[-1]）访问字符串时，str.__getitem__会执行以下步骤：

• 首先处理负索引：负索引会被自动转换为对应的正索引，转换规则是 正索引 = 字符串长度 + 负索引，例如string[-1]等价于string[len(string)-1]。
• 接着通过计算内存偏移量直接定位到目标字符的存储位置，因为字符串的元素在内存中是连续排列的，不需要遍历整个字符串就能直接取出对应位置的字符。

时间复杂度 #

str.__getitem__的时间复杂度是O(1)（常数时间）。无论字符串的长度是多少，下标访问操作只需要完成索引转换和一次内存定位，耗时与字符串长度完全无关。

示例验证 #

string = str(1001)  # 得到字符串"1001"
print(string[-1])  # 输出结果："1"

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