'abcde‘* 100的时间复杂度是多少？

Question

在Python 3中，时间复杂度是多少？

'abcde' * 100？是100还是500？

换句话说，对于长度为n的字符串，连接它的次数如下：

new_s = s * m

时间复杂度是O(mn)还是O(m)？谢谢!

Answer 1

幼稚的实现，如

new_s = s + s + s + s + s . . .

是O(m^2 * len(s))。但是，人们希望Python内部是聪明的，可以使用O(m * len(s))算法:创建一个适当长度的缓冲区，用s反复填充它，然后从缓冲区中创建一个结果字符串。