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

Компромиссы при решении динамических графовых задач (посмотреть исходный код)

151 байт добавлено , 19 июня 2018

4551

правка

Версия от 11:52, 19 июня 2018 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) ← Предыдущая правка		Версия от 11:55, 19 июня 2018 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) Следующая правка →
Строка 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>.