Блог пользователя Edvard

Автор Edvard, 12 лет назад, По-русски

Всем доброго времени суток!

Много раз при решении задач на деревья (n ≤ 5000) я сдавал динамики в которых квадрат состояний и линия переходов, но если поставить нужный отсек, то динамика работает очень быстро. К примеру нужно нам посчитать количество деревьев таких, что ровно k вершин обладают нужным нам свойством. Я обычно пишу динамику (v, cnt) — решаем задачу для поддерева вершины v при k = cnt. Тупой переход в такой динамике делается за O(cnt) — заводим еще одну динамику по сыновьям и для текущего сына перебираем какое ncnt ≤ cnt мы отдадим ему. Так вот грубая оценка такой динамики O(nk2). Но на деле если поставить отсечение в переборе ncnt ≤ количество вершин в поддереве, то такая динамика будет работать очень быстро. Я слышал, что на самом деле асимптотика здесь O(nk). Умеет это кто-нибудь доказывать? Аналогичный вопрос если делать отсечение по количеству листьев в поддереве.

  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Мне кажется, что я умею доказывать O(n2) (если k = n):

  1. Рассмотрим вершину. Пусть поддеревья её детей имеют размеры x1, x2, ..., xl. Тогда при первом переходе внутренней динамики мы следаем x1x2 операций. При втором — (x1 + x2)x3. При третьем — (x1 + x2 + x3)x4.
  2. Раскроем все скобки, получим сумму попарных произведений размеров поддеревьев.
  3. Заметим, что каждая единица в таком произведении — это два ребёнка, лежащие в разных поддеревьях. То есть мы являемся для них LCA.
  4. Таким образом, оценили время работы как суммарное количество LCA для всех пар вершин. O(n2).

Так как листьев в поддереве не больше, чем вершин, то для той динамики также верна квадратичная оценка.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Да круто теперь все понятно. Я про листья спросил потому, что думал, что может быть с листьями это быстро работает, а с поддеревом нет.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Классный, кстати, факт. Раньше не знал, спасибо :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится

        Ну про деревья есть 2 таких классных факта. Это первый, а второй то что можно мерджить меньшее поддерево к большему и получится O(nlog2n).

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

          без квадрата log

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Ну там еще один log от сета.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Нет, ну если именно подвешивать меньшее к большим, то получается чистый log допустим если используешь hashtable и т.п. Или вектора.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          И O(n) если параметр не кол-во вершин а высота поддерева.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Интересно, похоже на правду. А как доказывается линейная оценка?

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Можно представить, что мы продаём вершины и платим полученными деньгами за слияния. Действуем так, чтобы самый длинный путь в поддереве всегда оставался непроданным.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Имеется ввиду, что для каждой высоты хранится только одна вершина?

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Не очень понял. А что делать в случае с бамбуком? У нас есть высоты от 1 до x в вершине на глубине n - x. Итого квадрат.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              При мёрже у большего списка кол-во элементов увеличивается на 1, а меньший убивается. Тут будет n добавлений в список.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Что именно имелось в виду про слияние деревьев? Можно подробней?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

Альтернативное доказательство:

  1. Не теряя общности, пусть наше дерево бинарное (вершину степени три v --> 1,2,3 можно преобразовать в v --> 1,x ; x --> 2,3)

  2. T(n) = max по x=1..n-2 { T(x) + T(n — x — 1) + x*(n-x-1) }. T(n) — максимальное время работы алгоритма на дереве из n вершин, а x — количество вершин в левом поддереве.

  3. Интуитивно находим T(n) : рассматриваем случай x=1 "линия с сучками" и x=n/2 "полное бинарное дерево". Утверждается, что это единственные возможные крайние случаи :-) Этот шаг можно использовать, чтобы перед доказательством угадать ответ.

  4. Доказываем строго, что T(n) <= n2. Воспользуемся индукцией, т.е. для всех меньших n неравенство уже доказано. Тогда T(n) <= x2 + (n - x - 1)2 + x*(n-x-1) <= (x + (n - x - 1))2 <= (n - 1)2.

  5. Чем это доказательство лучше? По-моему, оно более универсальное. Т.е., если функция T(n) будет другая, приведенный метод поможет найти точную асимптотику.

P.S. Пример T(n) для задачи от автора поста: pdf

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Проверьте, верно ли такое:

Если в одном поддереве k1 вершин, а в другом k2, для слияния мы делаем О(k1+k2) операций. Рассмотрим на сколько позиций "упала" каждая вершина из обоих списков при переходе к объединённому списку, это будет O(k1 * k2), что больше k1 + k2 - 1. Но каждая вершина не может "падать" в сумме более чем на K поскольку у нас список по такой длине обрезается. То есть сумма "падений" точно O(N * k), а она больше чем число затраченных операций.

UPD. Это что же получается, если даже мы сливаем за k1 * k2, оно всё равно будет O(N * K)?