В питоне строки, с одной стороны, неизменяемые, т.к. только неизменяемые обьекты могут использоваться в качестве ключа в хеш-массивах, а с другой стороны, str+=str2 в CPython работает на месте за O(len(str2)). Как это сделано, что, с одной стороны, строки изменяемые, а с другой - по прежнему нет?

A id у строки тот же остается?

А откуда информация о сложности? Как я понимаю слияние строк сведется к вызову string_concat из stringobject.c. А там выделяется память под новую строку и копируется сначала содержимое первой, потом содержимое второй, так что O(len(str1)+len(str2)). Единственное там есть оптимизации для пустых строк.

PooH
А откуда информация о сложности?

Из документации.

CPython implementation detail: If s and t are both strings, some Python implementations such as CPython can usually perform an in-place optimization for assignments of the form s = s + t or s += t. When applicable, this optimization makes quadratic run-time much less likely. This optimization is both version and implementation dependent. For performance sensitive code, it is preferable to use the str.join() method which assures consistent linear concatenation performance across versions and implementations.