Среднее время выполнения Рабина-Карпа для длинных строк

Question

Мне сложно понять, почему среднее время выполнения для алгоритма Рабина-Карпа равно O (n + m), где n - длина входной строки, а m - длина строка шаблона. Насколько я понимаю, время выполнения должно быть O (n + m) для всех n и m, даже если n и m очень большие.

Пусть наша функция хеширования возвращает целые числа от 1 до k. Тогда вероятность ложного столкновения в каждой позиции равна 1 / k, поэтому мы ожидаем получить в среднем O (n / k) ложных столкновений в дополнение к одному правильному совпадению хеширования (если совпадение есть). Таким образом, мы ожидаем O (1 + n / k) совпадений хеширования. Каждый раз, когда мы получаем совпадение, мы должны проверять в среднем O (m) символов, поэтому общее среднее время выполнения составляет O ((1 + n / k) * m).

Для малых n (n < > k), это O (n / k m) = O (n m). Таким образом, средняя сложность выполнения составляет O (n m) для больших n, что означает, что среднее время выполнения теоретически составляет O (n m), а не O (n + m). Но, конечно, обычно мы находимся в режиме n <

Answer 1

Во-первых, ваш анализ неверен. размер ха sh - это log (k), а не k.

Во-вторых, обычное предположение состоит в том, что размеры вещей соответствуют постоянному количеству машинных слов, и что вы можете выполнять с ними математические операции за постоянное время.

Поскольку вам нужно k ~ n, ha sh также вписывается в машинное слово, и вы можете обновлять ha sh за постоянное время.