python - 字符串比较的时间复杂度

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)。

但是，我正在阅读这篇文档:Complexities of Python Operations

部分:

最后，当比较两个列表是否相等时，上面的复杂性类别显示为 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.