SeptiM Feb 9 2016 at 19:17

Компоненты связности в динамическом графе за один проход

8 min

19K

Образовательные проекты JetBrains corporate blogAlgorithms*Mathematics*

Tutorial

+19

Comments 7

zim32 Feb 10 2016 at 02:28

Сколько и где надо учиться чтобы понимать о чем идет речь в таких статьях?
Где-то с середины совсем потерялся

SeptiM Feb 10 2016 at 09:09

Эх… А где именно потерялись?
Зависит от начального уровня. Здесь нужно за спиной иметь базовые алгоритмы, графы и теорию вероятностей.

zim32 Feb 10 2016 at 13:09

Да вроде базовые есть. Но это как учить язык. Без применения на практике видимо все быстро улетучивается

rinaskela Feb 10 2016 at 15:23

Вероятно, на этом месте.

Возьмем случайную 2-независимую хэш-функцию h: [n] \rightarrow [2s]. Эта такая функция, которая два произвольных различных ключа распределяет равновероятно независимо. Возьмем хэш-таблицу размера 2s. В каждой ячейке таблицы будет сидеть алгоритм для 1-разереженного вектора.

Здесь начинается резкое повышение сложности формулировок.
И еще, правильно ли будет сказать, что прохождение теста неподходящим нам вариантом (с ненулевой вероятностью) связано с ограничениями по памяти?

SeptiM Feb 10 2016 at 16:44

Да, проблема.

По поводу 1-разреженных векторов и проверок. Да, мы хотим уместить память алгоритма в $O(\log^c n)$ . Если не дать алгоритму ошибаться, нижняя оценка по памяти взлетит до $\Omega(n)$ . Это на самом деле несложно показать.

Представьте, что у вас есть алгоритм, который умеет детерминированно определять, осталась в векторе ровно одна ненулевая позиция или нет. Возьмем множество $S \subseteq [n]$ размера $n / 2$ и кинем обновления $(i, +1)$ для всех $i \in S$ . После обработки всех обновлений алгоритм сформирует слепок памяти. Вот я утверждаю, что из этого слепка можно восстановить все множество $S$ . Поскольку всего таких множеств $\Omega(2^n / n)$ , то размер слепка будет порядка $\Omega(n)$ .

Восстанавливать просто: перебираем все подмножества $T \subseteq [n]$ размером $n / 2 - 1$ и кидаем обновления $(i, -1)$ . Если угадали подмножество $S$ , то результат будет 1-разреженным вектором и алгоритм вернет True, иначе – False. Берем объединение по всем хорошим $T$ и получаем $S$ .

SeptiM Feb 10 2016 at 17:45

Сделал вставку про хэш-функции в этом месте.

poxvuibr Feb 10 2016 at 13:33

Начните с курса на курсере. Очень интересно и очень просто. www.coursera.org/course/algs4partI