Компромиссы при решении динамических графовых задач: различия между версиями

Перейти к навигации Перейти к поиску
Строка 103: Строка 103:




Положив k = (nlogn)1/2 и (nlogn)1/2 < t < n3/4 (log n)1/4 в теореме 7, можно получить амортизированное время обновления O(mn 22l°gn) и время выполнения запросов в наихудшем случае O(t). Самое быстрое время обновления, O(mn), можно получить, если выбрать t = n3/4(log n)1/4.
Положив <math>k = (n \; log \; n)^{1/2}</math> и <math>(n \; log \; n)^{1/2} \le t \le n^{3/4} \; (log \; n)^{1/4}</math> в теореме 7, можно получить амортизированное время обновления <math>O(\frac{m \; n^2 \; log \; n}{t^2})</math> и время выполнения запросов в наихудшем случае O(t). Самое быстрое время обновления, <math>O(m \sqrt{n \; log n})</math>, можно получить, если выбрать <math>t = n^{3/4}(log \; n)^{1/4}</math>.




Источник — http://pco.iis.nsk.su/wega/index.php/Компромиссы_при_решении_динамических_графовых_задач