Python取子串是O(n)操作吗？与C++实现对比及性能疑问

问题解答 #

1. C++ std::string substr操作的时间复杂度纠正 #

你对C++ substr的时间复杂度认知存在偏差。标准库的std::string是拥有独立内存所有权的容器，调用substr(1)时会申请新的内存空间，复制从偏移1开始的所有字符到新内存，再赋值给原变量，所以时间复杂度是O(k)，k为子串的长度，并非O(1)。
只有C17引入的std::string_view做子串截取才是O(1)的，它仅持有原字符串的指针和长度，不会复制数据。
对应的C示例代码：

string s = "myreallylongstring";
s = s.substr(1);

2. Python字符串切片s[1:]的时间复杂度 #

是的，这个操作的时间复杂度确实是O(n)。
Python的字符串是不可变对象，不允许直接修改原内存中的数据，所有切片操作都会生成全新的字符串，将目标区间的字符全量复制到新的内存空间，所以切片长度是多少，时间复杂度就对应为线性等级。
对应的Python示例代码：

s = "myreallylongstring"
s = s[1:]

3. 改用字符列表的性能对比 #

如果只是单次做移除首字符的操作，用字符列表不会更快，反而效率更低：

• 首先把字符串转成字符列表list(s)本身就有O(n)的开销
• 列表pop(0)操作也是O(n)的时间复杂度，需要把后续所有元素向前移动一位，且这个操作是Python层的逻辑，比字符串切片底层C实现的效率低很多。
  如果你的场景需要频繁对字符串做头部增删操作，可以用collections.deque容器，它的popleft()是O(1)的操作，等所有修改完成后再一次性join成字符串，整体效率会高很多。

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