Временная сложность сравнения строк

Question

Я провел какой-то тест, чтобы определить, является ли O (==) для строк O (len (строка)) или 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)

LookingПри указанных выше результатах я понимаю, что сравнение строк является линейным O (N), а не O (1).

Однако я читал этот документ: Сложности операций Python

Часть:

Наконец, при сравнении двух списков на равенство вышеприведенный класс сложности отображается как O (N), но в действительности нам нужно умножить этот класс сложности на O == (...) где O == (...) - класс сложности для проверки, являются ли два значения в списке ==.Если они целые, O == (...) будет O (1);если они являются строками, O == (...) в худшем случае это будет O (len (string)).Эта проблема возникает всякий раз, когда выполняется проверка ==.В основном мы будем предполагать, что == проверка значений в списках - это O (1): например, проверка целочисленных значений и строк малой / фиксированной длины.

Это говорит о том, что худшим случаем для строк будет O (len).(строка)).Мой вопрос, почему наихудший случай?Разве лучший (средний) случай не должен быть O (len (string))?

Answer 1

Алгоритм прост, вы проверяете строки char по char, поэтому:

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.