4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 30: | Строка 30: | ||
'' | '' | ||
Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал <math>\Phi\ = k \cdot D(S,A) + \sum_{i<j}d(s_{i}, s_{j})</math> | |||
, где D(S,A) – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма <math>\Phi\ </math> и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]: | Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал <math>\Phi\ = k \cdot D(S,A) + \sum_{i<j}d(s_{i}, s_{j})</math>, где <math>D(S,A) \, </math> – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма <math>\Phi\ </math> и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]: | ||
'''Теорема: Алгоритм DC-TREE является k-конкурентным на деревьях.''' | '''Теорема: Алгоритм DC-TREE является k-конкурентным на деревьях.''' |
правок