Теория и практика защиты программ

Анализ алгоритма «Квадратного корня»


Как обсуждалось выше, последовательность фактических операций доступа к памяти забывающей RAM-машины действительно не открывает никакой информации относительно последовательности виртуальных операций доступа к памяти оригинальной RAM-машины. Это действительно так, потому что во время шагов 1, 2a, 2d и 3 фактическая модель доступа фиксирована, в то время как во время шагов 2b и 2c фактические модели доступа неразличимы и «случайны».

Теперь остается вычислить затраты на моделирование (т.е., отношение числа операций доступа, выполненных на забывающей RAM-машиной к числу оригинальных операций доступа). Далее мы вычисляем общее число фактических операций доступа, выполняемых на период (т.е., m+2

Анализ алгоритма «Квадратного корня»
 виртуальных операций доступа). Число фактических операций доступа на шаге 1 определено числом сравнений в сортирующей сети Батчера, а именно, O(mlog2m). То же самое делается на шаге 3. Что касается шага 2, каждая виртуальная операция доступа выполняется за 2
Анализ алгоритма «Квадратного корня»
+log2(m+
Анализ алгоритма «Квадратного корня»
)=O(
Анализ алгоритма «Квадратного корня»
) фактических операций доступа. Это составляет амортизационные затраты O(log2m
Анализ алгоритма «Квадратного корня»
). Фактически, вышеупомянутый выбор параметров (то есть, размер памяти зщт) не оптимален.

При использовании памяти зщт размера s, мы получаем амортизационные затраты

Анализ алгоритма «Квадратного корня»
,

которые минимизированы установкой s=Q(logm

Анализ алгоритма «Квадратного корня»
).



Содержание раздела






Главная сайта