字符串比较的时间复杂度

Question

我运行了一些测试来确定字符串的 O(==) 是 O(len(string)) 还是 O(1)。

我的测试：

import timeit
x = 'ab' * 500000000
y = 'ab' * 500000000
%timeit x == y
> 163 ms ± 4.62 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
x = 'ab' * 5000
y = 'ab' * 5000
%timeit x == y
> 630 ns ± 23.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

查看上述结果，我了解到字符串比较是线性 O(N) 而不是 O(1)。

但是，我正在阅读此文档：Python 操作的复杂性

部分：

最后，当比较两个列表的相等性时，上面的复杂度类显示为 O(N)，但实际上我们需要将此复杂度类乘以 O==(...)，其中 O==(...) 是用于检查列表中两个值是否为 == 的复杂度类。如果它们是整数，则 O==(...) 将是 O(1);如果它们是字符串，O==(...) 在最坏的情况下，它将是 O(len(string))。此问题适用于执行 == 检查的任何时候。我们通常假设 == 检查列表中的值是 O(1)：例如，检查整数和小/固定长度的字符串。

这表示字符串的最坏情况是 O(len(string))。我的问题是为什么最坏的情况？最好/平均的情况不应该是 O(len(string))吗？

Answer 1

算法很简单，你逐个查字符地检查字符串，所以：

Hello == Hello => They are equal...so it is actually the worst case because you check all the chars from both strings
Hello != Hella => Still worst case, you realize they are different in the last char of the strings.
hello != Hello => Best case scenario, the first char for both (h != H) are different, so you stop checking them there.