logo标签列表

字符串切片的时间复杂度是 O(k) 还是 O(n)？

pythonstringalgorithmtime-complexityslice
4

Python的字符串切片时间复杂度是O(k)还是O(n)？

我看到的答案表明它是O(k)，但我不理解为什么。

例如：

my_str = "thisismystringfortesting"

sub_str = my_str[3:10]

我知道它只提取(k)个字符，但这个操作在切片之前是否必须先将整个字符串转换为列表？ 我的思路是仅将整个字符串转换为列表就需要O(n)的时间复杂度。除非只有部分字符串被转换为列表？

那么请问有人能解释一下Python中字符串切片的时间复杂度是O(k)还是O(n)吗？

非常感谢！

3
为什么需要将整个字符串转换为列表？ - user2390182
如何对n和k非常不同的示例进行行为分析？ - MrSmith42
2
为什么需要中间列表呢？这个应该是用C实现的，而不是Python，所以它可以直接访问字符串的内部表示，并复制所请求的子字符串。 - Barmar
1个回答
7
相关代码在这里，它的时间复杂度为O(k)，可以从第1628行看出。
result_buf = PyBytes_AS_STRING(result);
for (cur = start, i = 0; i < slicelength;cur += step, i++) {
        result_buf[i] = source_buf[cur];
}
return result;
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接