两种Python字符串空格替换为%20方法的时间复杂度疑问解析

两个算法的时间复杂度没有差异，最终都是O(n)（n为输入字符串的长度），下面逐个拆解分析：

第一个算法的复杂度计算 #

1. 遍历字符串：循环逐个处理输入字符串的每个字符，这一步的时间复杂度是O(n)。
2. 列表append操作：题目明确append的均摊时间复杂度为O(1)，n次append的总时间是O(n)。
3. join拼接操作：''.join(arr)的时间复杂度由最终结果的总长度决定，记为m。每个空格会被替换为3个字符，因此m的范围是n（无空格）到3n（全空格），但m始终是O(n)级别的，所以join的时间复杂度为O(n)。
4. 总复杂度：O(n) + O(n) + O(n) = O(n)。

第二个算法的复杂度计算 #

这个算法用列表推导式替代了显式循环，本质和第一个算法逻辑一致：

1. 列表推导式遍历处理：遍历输入字符串的每个字符，做判断和替换，每个字符的处理是O(1)，总时间O(n)。
2. 列表构建：列表推导式底层和循环append的实现逻辑相近，每个元素的添加操作均摊O(1)，总时间O(n)。
3. join拼接操作：和第一个算法完全相同，时间复杂度O(n)。
4. 总复杂度：同样是O(n)。

关于join方法的时间复杂度 #

是的，对列表调用join的时间复杂度为O(m)（m为列表所有元素的总字符数）。因为join需要遍历列表中的每个元素，将所有字符逐个拷贝到最终字符串中，总操作数等于最终字符串的长度。在这个场景下，m是O(n)级别，所以join的时间复杂度为O(n)。

总结：两个算法只是写法不同，底层执行逻辑接近，时间复杂度都是线性的O(n)，不存在性能差异。

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