Python中startswith()方法的时间复杂度：与==运算符的Big O是否相同？

startswith()方法的时间复杂度 #

str.startswith(prefix) 的时间复杂度为 O(k)，其中k是前缀字符串的长度。它的逻辑是逐个比对原字符串的前k个字符与前缀：

• 若第一个字符就不匹配，直接终止，此时为O(1)；
• 若所有k个字符都匹配，才会走完整个比对流程，此时为O(k)。

==运算符的时间复杂度 #

字符串的==运算符时间复杂度为 O(n)，其中n是两个待比较字符串中较短的那个的长度：

• 首先会检查两个字符串的长度，若长度不等直接返回False，这一步是O(1)；
• 若长度相等，才会逐个比对每个字符，直到发现不匹配或全部比对完成，最坏情况为O(n)。

二者Big O复杂度是否一致？ #

这取决于具体的使用场景：

• 当你用startswith()比对的前缀长度等于原字符串长度（比如s.startswith(s)），此时它的最坏复杂度是O(n)，和==运算符比对两个等长字符串的最坏复杂度一致；
• 若用startswith()比对短前缀（比如s.startswith("test")），它的最坏复杂度是O(4)，而==比对整个字符串的最坏复杂度是O(n)（n远大于4时），此时二者Big O不同；
• 另外，两者都有快速失败的逻辑：startswith()若前缀长度大于原字符串长度，直接返回False；==若两字符串长度不等直接返回False，这部分都是O(1)操作。

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