Всем доброго времени суток!
Много раз при решении задач на деревья (n ≤ 5000) я сдавал динамики в которых квадрат состояний и линия переходов, но если поставить нужный отсек, то динамика работает очень быстро. К примеру нужно нам посчитать количество деревьев таких, что ровно k вершин обладают нужным нам свойством. Я обычно пишу динамику (v, cnt) — решаем задачу для поддерева вершины v при k = cnt. Тупой переход в такой динамике делается за O(cnt) — заводим еще одну динамику по сыновьям и для текущего сына перебираем какое ncnt ≤ cnt мы отдадим ему. Так вот грубая оценка такой динамики O(nk2). Но на деле если поставить отсечение в переборе ncnt ≤ количество вершин в поддереве, то такая динамика будет работать очень быстро. Я слышал, что на самом деле асимптотика здесь O(nk). Умеет это кто-нибудь доказывать? Аналогичный вопрос если делать отсечение по количеству листьев в поддереве.
Мне кажется, что я умею доказывать O(n2) (если k = n):
Так как листьев в поддереве не больше, чем вершин, то для той динамики также верна квадратичная оценка.
Да круто теперь все понятно. Я про листья спросил потому, что думал, что может быть с листьями это быстро работает, а с поддеревом нет.
Классный, кстати, факт. Раньше не знал, спасибо :)
Ну про деревья есть 2 таких классных факта. Это первый, а второй то что можно мерджить меньшее поддерево к большему и получится O(nlog2n).
без квадрата log
Ну там еще один log от сета.
Нет, ну если именно подвешивать меньшее к большим, то получается чистый log допустим если используешь hashtable и т.п. Или вектора.
И O(n) если параметр не кол-во вершин а высота поддерева.
Интересно, похоже на правду. А как доказывается линейная оценка?
Можно представить, что мы продаём вершины и платим полученными деньгами за слияния. Действуем так, чтобы самый длинный путь в поддереве всегда оставался непроданным.
Имеется ввиду, что для каждой высоты хранится только одна вершина?
Не очень понял. А что делать в случае с бамбуком? У нас есть высоты от 1 до x в вершине на глубине n - x. Итого квадрат.
При мёрже у большего списка кол-во элементов увеличивается на 1, а меньший убивается. Тут будет n добавлений в список.
Что именно имелось в виду про слияние деревьев? Можно подробней?
Альтернативное доказательство:
Не теряя общности, пусть наше дерево бинарное (вершину степени три v --> 1,2,3 можно преобразовать в v --> 1,x ; x --> 2,3)
T(n) = max по x=1..n-2 { T(x) + T(n — x — 1) + x*(n-x-1) }. T(n) — максимальное время работы алгоритма на дереве из n вершин, а x — количество вершин в левом поддереве.
Интуитивно находим T(n) : рассматриваем случай x=1 "линия с сучками" и x=n/2 "полное бинарное дерево". Утверждается, что это единственные возможные крайние случаи :-) Этот шаг можно использовать, чтобы перед доказательством угадать ответ.
Доказываем строго, что T(n) <= n2. Воспользуемся индукцией, т.е. для всех меньших n неравенство уже доказано. Тогда T(n) <= x2 + (n - x - 1)2 + x*(n-x-1) <= (x + (n - x - 1))2 <= (n - 1)2.
Чем это доказательство лучше? По-моему, оно более универсальное. Т.е., если функция T(n) будет другая, приведенный метод поможет найти точную асимптотику.
P.S. Пример T(n) для задачи от автора поста: pdf
Проверьте, верно ли такое:
Если в одном поддереве k1 вершин, а в другом k2, для слияния мы делаем О(k1+k2) операций. Рассмотрим на сколько позиций "упала" каждая вершина из обоих списков при переходе к объединённому списку, это будет O(k1 * k2), что больше k1 + k2 - 1. Но каждая вершина не может "падать" в сумме более чем на K поскольку у нас список по такой длине обрезается. То есть сумма "падений" точно O(N * k), а она больше чем число затраченных операций.
UPD. Это что же получается, если даже мы сливаем за k1 * k2, оно всё равно будет O(N * K)?
Если рассмотреть что-то типа такого: http://ars.sciencedirect.com/content/image/1-s2.0-S0031320308000812-gr3.gif?
Предыдущее рассуждение относится к произвольной динамике, где мы сливаем за O(size1 * size2) [тогда в сумме имеем O(n2)], или за O(min(size1, k) * min(size2, k)) [тогда в сумме имеем O(nk)].
О, пришёл папка динамик на деревьях :) Можешь что-нибудь ещё к этому всему добавить? Мне правда интересно почитать.