Comments 12
Спасибо за статью, читал с интересом. Скажите мне, может я просто не вник, а сложность остается та же O(logN)? Я так понял, что на каждой итерации мы, по сути, задействуем поиск кратчайших путей, для определения медианы (а это тоже вносит свой вклад). В общем, вопрос сложности. Извините, если задаю глупые вопросы =)
сложность по времени не менее чем n log n, но запросов всего log. Если граф небольшой, а запрос выполняется долго, то это эффективно.

Подвох здесь чувствую я. Вы собрались в множестве из N элементов искать нужный за более чем O(n) операций???


Also, зачем вы говорите об ограничении снизу когда вас спрашивают об ограничении сверху?

У нас поиск медианы на каждом шаге долгий. Так что да, если запрос выполняется за константное время, быстрее будет перебрать все вершины графа
Расскажите сценарий в котором запрос будет выполняться за время зависящее от N.
Я вам синтетических примеров могу сколько угодно придумать — например, запрос, который n! считает прежде, чем ответ выдать.
А вот реальной применимости здесь не видно.

После еще нескольких перечитываний статьи я кажется начал понимать что хотел сказать автор.


Вот есть git bisect, который ищет между "хорошей" и "плохой" вершиной в DAG самую раннюю плохую. И минимизирует количество вопросов "является ли эта вершина плохой", т.к. время на получение ответа (который вообще может считаться вручную) непредсказуемо и предполагается много бОльшим чем обходы графа.


Автор хочет сделать что-то похожее, только в более общем виде — на произвольном графе.

Но по постановке задачи автора, тот кто отвечает на вопросы (и чьё время мы хотим сэкономить) сразу знает точный ответ и становится непонятно зачем выяснять его таким странным способом. Надо подумать как видоизменить задачу так, чтобы изначально ни у одной из сторон ответа не было.
В противном случае пусть e=(v,w) будет ребром, полученным в ответ на запрос; вычисляем множество всех вершин x∈V, для которых e является кратчайшим путём из v в x. Назовём это множество T.


И что вот здесь вот с big-O происходит?
self.distance_from_start[vertex] = new_distance

if new_distance < self.distance_from_start[vertex]:

Здесь ошибка. Присвоение, а потом сравнение с тем же самым значением.

Граф выглядит как дерево с равномерными весами

Хм тавтология какая то… Дерево это связный ациклический граф, следовательно выходит: граф выглядит как граф. Если смотреть оригинал:


Graph looks like this tree, with uniform weights

То тоже немного тавтологией отдает, но не так.

Only those users with full accounts are able to leave comments. Log in, please.