Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 12

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

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


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

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

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


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


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

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


И что вот здесь вот с big-O происходит?
Всего голосов 1: ↑1 и ↓0+1
self.distance_from_start[vertex] = new_distance

if new_distance < self.distance_from_start[vertex]:

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

Всего голосов 1: ↑1 и ↓0+1
Граф выглядит как дерево с равномерными весами

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


Graph looks like this tree, with uniform weights

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

Всего голосов 2: ↑1 и ↓10
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Показать лучшие за всё время
Разблокировать темную тему

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr