Python 3中'string' * m的时间复杂度是O(mn)还是O(m)？

• 结论：对于长度为n的字符串s，执行new_s = s * m的时间复杂度是O(mn)，而非O(m)。
• 对应到'abcde' * 100的场景，原字符串长度n=5、重复次数m=100，操作量级对应5×100=500，属于O(500)范畴。

核心原因： #

Python中的字符串是不可变序列，执行乘法操作时，不会逐次做m次拼接，而是直接计算最终字符串的总长度（n*m），一次性分配足够的内存空间，再将原字符串的内容连续复制m次到新内存中。整个过程的总操作量完全取决于最终字符串的总长度，也就是n与m的乘积，因此时间复杂度为O(mn)。

比如'abc' * 3会直接生成'abcabcabc'，底层是一次性完成9个字符的复制操作，总工作量和最终字符串长度直接挂钩，而非仅和重复次数m相关。

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