Почему этот алгоритм работает для Quadrati c Probing? - PullRequest
Новая
       21

Почему этот алгоритм работает для Quadrati c Probing?

0 голосов
/ 15 марта 2020

Почему увеличение смещения на 2 имеет смысл? Я знаю, что этот алгоритм работает, я составил результаты, которые привели к графику типа ax ^ 2, но я просто не вижу его. Может ли кто-нибудь объяснить это простыми словами? Спасибо! 

        size_t FindPos(const HashedObj & x) const {
        size_t offset = 1;
        size_t current_pos = InternalHash(x);

        while (array_[current_pos].info_ != EMPTY && array_[current_pos].element_ != x) {
           current_pos += offset;  
           offset += 2;
           if (current_pos >= array_.size())
              current_pos -= array_.size();
           }
       return current_pos;
      }

1 Ответ

0 голосов
/ 15 марта 2020

Вы увеличиваете offset на 2 в каждой итерации, поэтому после n -ой итерации if будет иметь значение 1+2*n.

Вы добавляете это значение к current_pos в каждой итерации. итерация. Итак, в первой итерации вы добавляете 1+0*2 к current_pos, во второй вы добавляете 1+1*2, в третьей 1+2*2 и т. Д.

Общая сумма добавляется к current_pos следовательно, к концу m -ой итерации тела будет сумма 1+2*n от n=0 до n=m-1, без учета операции по модулю на мгновение.

Использование линейности сложения эта сумма может быть записана как m + 2 * sum(n for n=0 to m-1). Можно показать, что оставшаяся сумма оценивается как m*(m-1)/2, так что итоговое значение равно 

m + 2 * m*(m-1)/2 = m**2

. Таким образом, этот метод делает то же самое, что и использование (current_pos + m**2) % array_.size() в каждой итерации с m, равным l oop Счетчик и без изменения current_pos будет.

...