Ресинхронизация схемы: инкрементный подход: различия между версиями

В базовом алгоритме оптимальность P3 проверяется условием <math>r[v] \ge |V| \;</math>. Однако в большинстве случаев условие оптимальности можно обнаружить намного раньше. Поскольку при каждом возрастании r[v] должна существовать «вершина-хранитель» u, такая, что после выполнения действия будет верно неравенство <math>r[u] - r'[u] \ge r[v] - r'[v] \;</math>. Следовательно, если ввести указатель из v на u при увеличении r[v], указатели не смогут образовать цикл согласно <math>\neg P3</math>. Фактически указатели образуют лес, в котором корни имеют значение r = 0, а потомок может иметь значение r, не более чем на 1 превышающее значение его предка. Использование цикла указателей как свидетельство верности P3 вместо <math>r[v] \ge |V| \;</math>, можно значительно повысить практическую эффективность алгоритма.