не вычисляет ли значение хеша путем полиномиальной прокатки для строки O (n), где n - размер строки?

Question

Просто прочитайте о строковом хешировании и полиномиальной хеш-функции для его вычисления.Для меня это выглядит так, как будто временная сложность вычисления хэша (строки) равна O (N), где 'N' - это размер строки

long long compute_hash(string const& s) {
 const int p = 31;
 const int m = 1e9 + 9;
 long long hash_value = 0;
 long long p_pow = 1;
 for (char c : s) {
     hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
     p_pow = (p_pow * p) % m;
 }
 return hash_value;
}

Где можно вычислить хеш-значение строки 'S'как S[0] + S[1].P + S[2].P.P + . . . S[N - 1].P^(N - 1)

И если вычисление O (N), то не хэширует ли N строк O (N ^ 2)?

Answer 1

Да, хеширование N строк длины N - это процесс O (N²).(Хотя на практике такой случайный случай встречается очень редко.)

Answer 2

Короткий ответ : если вы вставили n строк длиной n , рассуждения верны, но в "сценарии" длина строк равнаопределяется числом строк для хеширования, это бит странно .

И если вычисление O (N), то не хэширование N строк равно O (N *)1012 * 2 )?

При условии, что длина строк масштабируется с количеством строк, то для данного алгоритма хеширования это действительно приведет к O (n ² ) .Но обычно нет никакой корреляции между длиной строки и числом строк в хэше.

Если строки имеют среднюю длину k , и есть n строк, то это алгоритм O (n × k) .Таким образом, вы правы в том, что «размер» объектов может влиять на производительность, учитывая, конечно, что алгоритм хеширования масштабируется с размером объекта.