Главная страница
Навигация по странице:

  • 15.1. Квадратный корень в алгоритмах

  • 15.1.1. Структуры данных

  • Рис. 15.1.

  • Размер входных данных n Время выполнения O(log n ) (с) Время выполнения O(√ n ) (с) Время выполнения

  • 15.1.2. Подалгоритмы

  • Расстояние между буквами.

  • Рис. 15.4.

  • Таблица 15.2.

  • 15.1.3. Целые разбиения

  • Рис. 15.6.

  • 15.1.4. Алгоритм Мо

  • анти. Guide to Competitive


    Скачать 2.39 Mb.
    НазваниеGuide to Competitive
    Дата20.12.2022
    Размер2.39 Mb.
    Формат файлаpdf
    Имя файлаанти.pdf
    ТипGuide
    #854732
    страница21 из 26
    1   ...   18   19   20   21   22   23   24   25   26
    Глава
    15
    Дополнительные темы
    В этой последней главе представлена подборка дополнительных алгорит- мов и структур данных. Свободное владение изложенными здесь методами иногда может помочь при решении наиболее трудных олимпиадных задач.
    В разделе 15.1 обсуждаются приемы создания структур данных и алго- ритмов, в которых встречается квадратный корень. В основе решения за- частую лежит идея о разбиении последовательности n элементов на O(√n)
    блоков, каждый из которых состоит из O(√n)элементов.
    В разделе 15.2 рассматриваются дополнительные возможности дерева отрезков. Например, мы увидим, как создать дерево отрезков, которое поддерживает как запросы по диапазону, так и обновление диапазона.
    В разделе 15.3 представлена структура данных «дуча» (дерево-куча), позволяющая эффективно разбить массив на две части и объединить два массива в один.
    Раздел 15.4 посвящен оптимизации метода динамического программи- рования. Сначала мы рассмотрим трюк с выпуклой оболочкой, который применяется для линейных функций, а затем обсудим его оптимизацию методом «разделяй и властвуй» и оптимизацию Кнута.
    В разделе 15.5 рассматриваются различные приемы проектирования алгоритмов, в частности встреча в середине и параллельный двоичный поиск.
    15.1. Квадратный корень в алгоритмах
    Квадратный корень можно рассматривать как «логарифм для бедных»: сложность O(√n)лучше, чем O(n), но хуже, чем O(log n). Так или иначе, многие структуры данных и алгоритмы, в которых участвуют квадратные корни, оказываются быстрыми и практичными. В этом разделе приведено несколько примеров использования квадратного корня в проектировании алгоритмов.
    15.1.1. Структуры данных
    Иногда эффективная структура данных получается, если разбить мас- сив на блоки размера √n и хранить информацию о значениях элементов

    280
    Глава 15. Дополнительные темы массива внутри каждого блока. Например, предположим, что требуется обрабатывать запросы двух типов: модификация элементов массива и на- хождение минимального значения в диапазоне. Выше мы видели, что де- рево отрезков способно поддержать выполнение обеих операций за время
    O(log n), а сейчас решим эту задачу проще, согласившись на временную сложность O(√n).
    Разобьем массив на блоки по √n элементов и для каждого блока будем хранить минимальное значение в нем. На рис. 15.1 показан массив из
    16 элементов, разбитый на блоки по 4 элемента. При изменении значения любого элемента необходимо модифицировать соответствующий блок.
    Это можно сделать за время O(√n), просмотрев все элементы блока, как показано на рис. 15.2. Затем для вычисления минимального значения по диапазону мы разобьем диапазон на три части: одиночные элементы по краям и блоки между ними. На рис. 15.3 показан пример такого разбиения.
    Ответом на запрос является либо значение какого-то из одиночных эле- ментов, либо минимум в одном из блоков. Поскольку и число одиночных элементов, и число блоков равно O(√n), то запрос выполняется за время
    O(√n).
    5 8
    6 3
    4 7
    2 6
    7 1
    7 5
    6 2
    3 2
    3 2
    1 2
    Рис. 15.1. Структура на основе квадратного корня для поиска минимального значения в диапазоне
    5 8
    6 3
    4 7
    5 6
    7 1
    7 5
    6 2
    3 2
    3 4
    1 2
    Рис. 15.2. При обновлении элемента массива необходимо также обновить минимальное значение в соответствующем блоке
    5 8
    6 3
    4 7
    2 6
    7 1
    7 5
    6 2
    3 2
    3 2
    1 2
    Рис. 15.3. Для определения минимального значения в диапазоне этот диапазон разбивается на одиночные элементы и блоки
    Насколько эта структура эффективна на практике? Чтобы выяснить это, мы поставили эксперимент: создали массив, содержащий n случайных чи- сел типа int
    , и обработали n случайных запросов о минимуме. Мы реали- зовали три структуры данных: дерево отрезков с временной сложностью запроса O(log n), описанную выше структуру на основе квадратного корня с временной сложностью O(√n) и простой массив с временной сложно-

    15.1. Квадратный корень в алгоритмах

    281
    стью O(n). Результаты сведены в табл. 15.1. Оказалось, что для этой задачи структура на основе квадратного корня вполне эффективна для значений
    n
    , не превышающих 2 18
    , но потом время выполнения заметно уступает де- реву отрезков.
    Таблица 15.1. Время выполнения запроса о минимуме в диапазоне при использова- нии трех структур данных: дерева отрезков (O(log n)), структуры на основе квадратно- го корня (O(√n
    )) и простого массива (O(n))
    Размер входных
    данных n
    Время выполнения
    O(log n) (с)
    Время выполнения
    O(√n
    ) (с)
    Время выполнения
    O(n
    ) (с)
    2 16 0.02 0.05 1.50 2
    17 0.03 0.16 6.02 2
    18 0.07 0.28 24.82 2
    19 0.14 1.14
    > 60 2
    20 0.31 2.11
    > 60 2
    21 0.99 9.27
    > 60
    15.1.2. Подалгоритмы
    Далее мы обсудим две задачи, которые можно эффективно решить пу- тем создания двух подалгоритмов, специализированных для различных ситуаций, которые могут иметь место в процессе выполнения алгоритма.
    И хотя каждый подалгоритм может решить задачу без использования дру- гого, их комбинирование повышает общую эффективность.
    Расстояние между буквами. Первая задача ста- вится следующим образом: дана сетка n×n, в каждой клетке которой находится буква. Каково минимальное манхэттенское расстояние между двумя клетками, со- держащими одну и ту же букву? На рис. 15.4 минималь- ное расстояние между клетками, содержащими букву
    «D», равно 2.
    Для решения задачи мы можем перебрать все буквы в сетке и для каждой буквы c определить минимальное расстояние между клетками, содержащими эту букву.
    Рассмотрим два алгоритма обработки фиксированной буквы c.
    Алгоритм 1. Перебрать все пары клеток, содержащих букву c, и опре- делить пару, для которой расстояние минимально. Этот алгоритм требует времени O(k
    2
    ), где k – число клеток, содержащих букву c.
    Алгоритм 2. Выполнить поиск в ширину, одновременно начинающийся во всех клетках с буквой c. Этот поиск занимает время O(n
    2
    ).
    A
    C
    E
    A
    B
    D
    F
    D
    E
    A
    B
    C
    C
    F
    E
    A
    Рис. 15.4. Пример задачи о рас- стоянии между буквами

    282
    Глава 15. Дополнительные темы
    Для обоих алгоритмов имеются худшие случаи. Для алгоритма 1 это слу- чай, когда буквы во всех клетках одинаковы, тогда k = n
    2
    , и время рабо- ты алгоритма составляет O(n
    4
    ). Для алгоритма 2 худшим является случай, когда буквы во всех клетках разные. Тогда алгоритм придется выполнить
    O(n
    2
    )раз, и общее время работы составит O(n
    4
    ).
    Однако мы можем скомбинировать эти алгоритмы, так чтобы они рабо- тали как подалгоритмы одного алгоритма. Идея в том, чтобы для каждой буквы c по отдельности определить, какой алгоритм использовать. Оче- видно, что алгоритм 1 хорошо работает, если k мало, а алгоритм 2 лучше приспособлен для больших k. Следовательно, мы можем зафиксировать константу x и применять алгоритм 1, если k не больше x, и алгоритм 2 в противном случае.
    В частности, если выбрать x = √n
    2
    = n, то получится алгоритм с временной сложностью O(n
    3
    ). Сначала каждая клетка, обрабатываемая алгоритмом 1, сравнивается не более чем с n другими клетками, так что обработка зани- мает время O(n
    3
    ). Затем, поскольку существует не более n букв, которые могут встречаться более чем в n клетках, алгоритм 2 выполняется самое большее n раз, и общее время работы также равно O(n
    3
    ).
    Черные клетки. В качестве еще одного примера рассмотрим следую- щую игру. На доске n×n имеется ровно одна черная клетка, а все осталь- ные белые. На каждом ходе выбирается одна белая клетка, и мы должны вычислить минимальное манхэттенское расстояние между ней и черной клеткой. Затем выбранная белая клетка перекрашивается в черный цвет.
    Этот процесс повторяется n
    2
    − 1 раз, после чего все клетки оказываются черными.
    На рис. 15.5 показан один ход в игре. Минимальное расстояние от вы- бранной клетки X до черной клетки равно 3 (надо сделать два шага вниз и один шаг вправо). После этого клетка перекрашивается в черный цвет.
    X
    Рис. 15.5. Ход в игре в черные клетки.
    Минимальное расстояние от X до черной клетки равно 3
    Эту задачу можно решить, обрабатывая ходы порциями по k ходов. В на- чале каждой порции мы для каждой клетки доски вычисляем минималь- ное расстояние до черной клетки. Это можно сделать за время O(n
    2
    ), при- менив поиск в ширину. Далее в процессе обработки порции мы храним

    15.1. Квадратный корень в алгоритмах

    283
    список всех клеток, которые были перекрашены в черный цвет в текущей порции. Таким образом, минимальное расстояние до черной клетки либо предварительно вычислено, либо является расстоянием до одной из кле- ток в списке. Поскольку список содержит не более k значений, то для его обхода требуется время O(k).
    Следовательно, взяв k = √n
    2
    = n, мы получим алгоритм, работающий за время O(n
    3
    ). Во-первых, существует O(n)порций, поэтому полное время, затраченное на поиски в ширину, равно O(n
    3
    ). Во-вторых, список клеток в порции содержит O(n)значений, поэтому вычисление минимальных рас- стояний для O(n
    2
    )клеток также требует времени O(n
    3
    ).
    Оптимизация параметров. На практике необязательно использовать в качестве параметра точный квадратный корень, нужно лишь настро- ить производительность алгоритма, поэкспериментировав с различными значениями параметров и выбрав то, которое дает наилучший результат.
    Разумеется, оптимальное значение зависит от алгоритма и от свойств тес- товых данных.
    В табл. 15.2 приведены результаты эксперимента, в котором алгоритм игры в черные клетки с временной сложностью O(n
    3
    )выполнялся для раз- личных значений k при n = 500. Порядок перекрашивания клеток в черный цвет выбирался случайным образом. В данном случае оптимальным, по- хоже, является параметр k в районе2000.
    Таблица 15.2. Оптимизация значения параметра k в алгоритме игры в черные клетки
    Параметр k
    Время работы (с)
    200 5.74 500 2.41 1000 1.32 2000 1.02 5000 1.28 10 000 2.13 20 000 3.97
    15.1.3. Целые разбиения
    Пусть имеется палочка длины n, разрезан- ная на несколько частей целочисленной дли- ны. На рис. 15.6 показано несколько таких разбиений для n = 7. Каково максимальное число различных длин в таком разбиении?
    Оказывается, что различных длин может быть не более O(√n). А оптимальный способ
    7 3
    4 1
    3 1
    2
    Рис. 15.6. Несколько целых разбиений палочки длины 7

    284
    Глава 15. Дополнительные темы получить максимально возможное число различных длин – взять длины
    1, 2, …, k. Тогда, поскольку
    1 + 2 + ··· + k = k (k + 1) ,
    2
    мы можем сделать вывод, что k не может быть больше O(√n). Далее мы увидим, как воспользоваться этим наблюдением при проектировании ал- горитмов.
    Задача о рюкзаке. Пусть дан список целых весов [w
    1
    ,w
    2
    ,…,w
    k
    ] – та- ких, что w
    1
    + w
    2
    + … + w
    k
    = n, а наша задача – найти все возможные сум- мы, составленные из этих весов. На рис. 15.7 показаны возможные суммы, составленные из весов [3, 3, 4].
    
    
    
    
    
    
    0 1
    2 3
    4 5
    6 7
    8 9
    10
    Рис. 15.7. Возможные суммы, составленные из весов [3, 3, 4]
    Применив стандартный алгоритм рюкзака (раздел 6.2.3), мы можем ре- шить задачу за время O(nk), так что если k = O(n), то временная сложность окажется равной O(n
    2
    ). Но поскольку различных весов не более O(√n), зада- чу можно решить эффективнее, если одновременно обрабатывать все веса, имеющие определенное значение. Например, если имеются веса [3, 3, 4], то мы сначала обработаем два веса, равных 3, а затем вес 4. Стандартный алгоритм рюкзака нетрудно модифицировать таким образом, что обра- ботка каждой группы одинаковых весов займет всего лишь время O(n), и в результате получается алгоритм с временной сложностью O(nn).
    Составление строки. Рассмотрим еще один пример. Пусть даны строка длины n и словарь, состоящий из слов суммарной длины m. Наша задача – посчитать, сколько существует способов составить строку из слов. Напри- мер, имеется четыре способа составить строку
    ABAB
    из слов
    {A
    , B, AB}
    :

    A + B + A + B
    ;

    AB + A + B
    ;

    A + B + AB
    ;

    AB + AB
    Применив динамическое программирование, мы для каждого k = 0, 1, ..., n
    сможем вычислить, сколькими способами можно составить префикс стро- ки длиной k. Одно из возможных решений – воспользоваться префиксным деревом, которое содержит обращения всех словарных слов, что дает алго- ритм с временной сложностью O(n
    2
    + m). Но есть и другой подход: восполь- зоваться хешированием строк и тем фактом, что существует не более O(√m)
    различных длин слов. Следовательно, можно ограничиться фактически

    15.1. Квадратный корень в алгоритмах

    285
    существующими длинами слов. Для этого мы можем создать множест во, содержащее все хеш-коды слов, что приводит к алгоритму с временной сложностью O(nm + m)(если воспользоваться классом unordered_set
    ).
    15.1.4. Алгоритм Мо
    Алгоритм Мо
    1
    обрабатывает множество запросов по диапазону стати-
    ческого массива (т. е. значения элементов массива не изменяются между запросами). Для ответа на каждый запрос требуется вычислить нечто, за- висящее от элементов массива в некотором диапазоне [a, b]. Поскольку массив статический, запросы можно обрабатывать в любом порядке, а изюминка алгоритма Мо состоит в том, чтобы выбрать специальный по- рядок, гарантирующий эффективность алгоритма.
    В алгоритме поддерживается активный диапазон массива, и в каждый момент ответ на запрос, касающийся активного диапазона, известен. Ал- горитм обрабатывает запросы по одному и каждый раз перемещает кон- цевые точки активного диапазона, вставляя и удаляя элементы. Массив разбивается на блоки по k = O(√n)элементов, и запрос [a
    1
    , b
    1
    ] всегда обра- батывается раньше запроса [a
    2
    , b
    2
    ], если
    • ⌊a
    1
    /k< a
    2
    /k⌋ или
    • ⌊a
    1
    /k⌋ = ⌊a
    2
    /k⌋ и b
    1
    < b
    2
    Таким образом, все запросы, для которых левые концевые точки нахо- дятся в некотором блоке, обрабатываются один за другим в порядке воз- растания правых концевых точек. При таком порядке алгоритм выполня- ет только O(nn)операций, поскольку левая концевая точка сдвигается на
    O(nO(√n
    )шагов, а правая концевая точка – на O(√nO(n)шагов. Следо- вательно, за время работы алгоритма обе концевые точки суммарно сдви- гаются на O(nn)шагов.
    Пример. Пусть дано множество диапазонов массива, и требуется вы- числить количество различных значений в каждом диапазоне. В алгоритме
    Мо запросы всегда сортируются одинаково, но способ хранения ответа на запрос зависит от задачи.
    Чтобы решить эту задачу, мы заведем массив count
    , в котором элемент count
    [x
    ] показывает, сколько раз элемент x встречается в активном диапа- зоне. При переходе от одного запроса к другому активный диапазон изме- няется. Рассмотрим, к примеру, два диапазона на рис. 15.8. Для перехода от первого диапазона ко второму надо сделать три шага: левая концевая точка сдвигается на один шаг вправо, а правая концевая точка – на два шага вправо.
    После каждого шага массив count следует обновить. Добавив элемент x, мы увеличиваем значение count
    [x
    ] на 1, и если после этого окажется, что
    1
    Согласно [6], алгоритм Мо назван в честь китайского олимпиадного программиста Мо Тао.

    286
    Глава 15. Дополнительные темы count
    [x
    ] = 1, то также прибавляем 1 к ответу на запрос. Аналогично, удалив элемент x, мы уменьшаем значение count
    [x
    ] на 1, и если после этого ока- жется, что count
    [x
    ] = 0, то также вычитаем 1 из ответа на запрос. Поскольку каждый шаг выполняется за время O(1), временная сложность алгоритма равна O(nn).
    4 2
    5 4
    2 4
    3 3
    4 4
    2 5
    4 2
    4 3
    3 4
    Рис. 15.8. Переход от одного диапазона к другому в алгоритме Мо
    15.2. И снова о деревьях отрезков
    Дерево отрезков – многоцелевая структура данных, применимая для ре- шения многих разных задач. До сих пор мы видели лишь небольшую часть ее возможностей. Пора обсудить более развитые варианты деревьев от- резков, позволяющие решать задачи посложнее.
    Выше при реализации операций с деревом отрезков мы поднимались
    снизу вверх. Так, для вычисления суммы значений в диапазоне [a, b] (раз- дел 9.2.2) использовалась следующая функция:
    1   ...   18   19   20   21   22   23   24   25   26


    написать администратору сайта