Что такое ожидаемая сложность проверки равенства двух произвольных струн?

Question

простой (наивный?) ответ будет o (n), где n - длина более короткой строки. Потому что в худшем случае вы должны сравнить каждую пару символов.

так далеко так хорошо. Я думаю, что мы все можем согласиться с тем, что проверка равенства два равных длины требует o (n) время выполнения.

Однако многие (большинство?) Языки (я использую Python 3.7) хранить длины струн, чтобы обеспечить постоянное поиск времени. Таким образом, в случае двух царственных строк вы можете просто проверить len(string_1) != len(string_2) в постоянное время. Вы можете убедиться, что Python 3 действительно делает эту оптимизацию.

Теперь, если мы проверяем равенство двух произвольных струн по-настоящему (произвольной длины), то она гораздо более вероятна (бесконечно, я верю), что строки будут неравной длины, чем равной длины. Который (статистически) гарантирует, что мы можем почти всегда сравнивать их в постоянном времени.

Итак, мы можем сравнить две произвольные строки в среднем o (1) с очень редким худшим случаем O (N). Должны ли мы рассмотреть строки сравнения, а затем быть O (1) таким же образом, мы считаем поиски хеш-таблицы, чтобы быть о (1)?

Answer 1

Чтобы обсудить ожидаемую временной сложность операции, вы должны указать распределение на входах, а также объяснить, что вы подразумеваете под $ n $ .

Нужно быть осторожным, однако. Например, рассмотрим предложение в комментариях, рассмотреть вопрос о некоторых видах распределения по поводу слов длины максимум 20. В этом случае сравнение строк четко $ O (1) $ , начиная с 20 - просто постоянная. Есть несколько способов избежать этого:

.

• Спроси не асимптотической сложности времени. Поскольку сложность времени сильно зависит от модели вычислений, вы можете рассчитывать (например) количество клеток входных памяти.

• Вы можете указать входное распределение, которое зависит от параметра $ m $ , а затем просить асимптотическую сложность с точки зрения $ m $ .

Вот пример. Учитывая две случайные двоичные строки длины $ n $ , в ожидании будет около 4 доступ. Напротив, если струны выбираются случайным образом из коллекции $ 0 ^ i1 ^ {ni} $ , количество доступов будет примерно $ (2/3) n $ . Эти два распределения могут быть разделены, даже если мы используем асимптотическое обозначение: алгоритм проходит в $ O (1) $ в первом распределении, а в $ \ theta (n) $ на втором.

Другая проблема - это значение $ n $ . Рассмотрим, например, строку $ 0 ^ m $ , где $ m \ sim g (1/2) $ это геометрическая случайная переменная. При запуске на входах длины $ a, b $ , время работы - $ \ theta (\ min (a, b )) $ . Как мы должны выразить это с точки зрения $ n= a + b $ ? Один выбор - спросить ожидаемое время работы, учитывая, что длина ввода составляет $ N $ . В таком случае, $$ \ mathbb {e} [\ min (a, b)]=sum_ {a= 1} ^ {n - 1} \ frac {(1/2) ^ a (1/2) ^ {N-1-A }} {\ sum_ {a '= 1} ^ {n-1} (1/2) ^ {A'} (1/2) ^ {N-1-A '}} \ min (A, Na)=frac {1} {n-1} \ sum_ {a= 1} ^ {n - 1} \ min (a, na) \ Приблизительно \ frac {n} {4}, $$ Таким образом, ожидаемое время работы составляет $ \ theta (n) $ .