4551
правка
Ресинхронизация схемы: инкрементный подход: различия между версиями
Перейти к навигации
Перейти к поиску
м
Ресинхронизация схемы: инкрементный подход (посмотреть исходный код)
Версия от 22:23, 2 июля 2017
, 2 июля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 245: | Строка 245: | ||
Корректность алгоритма можно легко показать в силу того, что P1 остается инвариантом и из отрицания предикатов следует P0 | Корректность алгоритма можно легко показать в силу того, что P1 остается инвариантом и из отрицания предикатов следует <math>P0 \and P2 \and P3 \;</math>. Завершение работы алгоритма гарантируется монотонным возрастанием r и его верхней границей. Следующая теорема задает время выполнения в наихудшем случае. | ||
'''Теорема 1. Время выполнения данного алгоритма ресинхронизации в наихудшем случае ограничено сверху значением <math>O(|V|^2 \; |E|)</math>.''' | |||
Время выполнения алгоритма ресинхронизации в наихудшем случае будет актуальным в случае, когда каждое увеличение r приводит к «протягиванию» синхронизации по всей схеме (т.е. по |E| ребрам). Это верно только тогда, когда увеличение r перемещает все регистры в схеме. Однако в таком случае верхняя граница r равна 1, и время выполнения не превышает O( | |||
Время выполнения алгоритма ресинхронизации в наихудшем случае будет актуальным в случае, когда каждое увеличение r приводит к «протягиванию» синхронизации по всей схеме (т.е. по |E| ребрам). Это верно только тогда, когда увеличение r перемещает все регистры в схеме. Однако в таком случае верхняя граница r равна 1, и время выполнения не превышает O(|V| |E|). С другой стороны, если значение r велико, схема разбивается регистрами на несколько меньших фрагментов, в результате чего протягивание, вызванное увеличением одного r, ограничено деревом небольшого размера. | |||
== Применение == | == Применение == | ||