在 python 中取一个子字符串是 O(n) 操作吗？

Question

在 C++ 中，如果我要从字符串中删除第一个字符，它将类似于：

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

这将是 O(1)。 [如果我错了请纠正我]

但是在 Python 的“不可变字符串”世界中，这段代码运行的复杂度是 O(n) 吗？

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

如果我改用字符列表会不会更快一些？

Answer 1

在 Python 中切片任何内置类型（除了 memoryview）在一般情况下是 O(n)（主要例外是不可变实例的完整切片，通常 returns 原始实例而不复制它，因为不需要它）。

list 个字符无济于事；从 list 的开头删除一个字符是 O(n) （它必须将其上方的所有内容复制到一个插槽中）。 collections.deque 可以改进 big-O（它们可以从两端做 O(1) 弹出），但它也会比字符串消耗更多的内存和更多的内存碎片。

对于除最大字符串以外的所有字符串，即使存在这些 O(n) 低效问题，您通常也没有问题，因此除非您实际分析并发现它是问题的原因，否则我会坚持切片并顺其自然。

也就是说，你对 C++ 的看法是错误的； s = s.substr(1) 与 Python 的 s = s[1:] 没有区别。它们最终都复制了整个字符串，保存了第一个字符，C++ 移动分配回原始字符串，而 Python 将绑定到旧对象的原始名称替换为新名称（功能上非常相似的操作）。 s.substr(1) 甚至没有使用 std::string 的可变性功能； s.erase(0, 1) 实际上会就地擦除，改变原始字符串，但它仍然是 O(n) 因为所有其他字符都必须复制到space 以前被删除的字符消耗（我知道没有 std::string 实现允许存储从字符串开头的偏移量以找到真实数据，指向数据的指针指向始终是第一个分配的字节）。

Answer 2

这个答案解决了问题的 C++ 部分

s = s.substr(1);

创建一个新的临时字符串并将其复制到 s。操作是O(n).

更好的方法是：

s.erase(s.begin());

这仍然是 O(n) 但避免创建新对象和复制。

更好的方法是使用 std::string_view:

auto sv = std::string_view{s.begin() + 1, s.end()}.

这是 O(1)，因为它不会创建或更改任何字符串，它只是在现有字符串中创建一个视图。

在 python 中取一个子字符串是 O(n) 操作吗？

Is taking a substring in python an O(n) operation?

c++

python

time-complexity