Главная Промышленная автоматика.

») Эта функция принимает значения от О до 2т-1.

ке. в этой ситуации для выполнения t-й операции из о требуется время, пропорциональное /. Таким образом, чтобы добавить все п элементов к множеству S, расстановка может потребовать времени порядка п?.

Однако в смысле среднего времени этот процесс выглядит много лучше. Если значение h (а) с равной вероятностью может быть любым числом между О и т-1 и вставляется пт элементов, то при вставке t-ro элемента средняя длина того списка, в который он помещается, равна (t-т. е. всегда меньше 1. Поэтому среднее время, необходимое для вставки п элементов, есть 0(п). Если 0(п) операций УДАЛИТЬ и ПРИНАДЛЕЖАТЬ выполняются вместе с операциями ВСТАВИТЬ, то общее среднее время по-прежнему составляет 0{п).

Следует иметь в виду, что проведенный анализ предполагает, что размер т таблицы расстановки не меньше максимального размера п множества S. Однако п, как правило, заранее не известно. В таком случае разумнее всего подготовиться к построению последовательности таблиц расстановки Го, Ti, Та, . . ..

Сначала выбирается подходящее значение т для размера исходной таблицы Т 0. Затем, как только число элементов, вставленных в То, превзойдет т, строится новая таблица Ti размера 2/п и с помощью новой функции расстановки ») все элементы, находящиеся в данный момент в Го, перемещаются в таблицу Ti. Теперь старая таблица Г о больше не нужна. Вставка новых элементов в Ti продолжается до тех пор, пока число элементов не превзойдет 2т. В этот момент создается новая таблица Га размера 4т и меняется функция расстановки, чтобы переместить старые элементы из Г в Га. Вообще всякий раз, когда в таблице Т оказывается 2*-im элементов, строится таблица Th размера 2%. Процесс продолжается до тех пор, пока не будут исчерпаны все элементы.

Подсчитаем среднее время, требуемое для вставки в таблицу расстановки 2* элементов, если применять изложенную только что схему и считать /п=1. Легко видеть, что этот процесс описывается рекуррентным уравнением

Г(1)=1,

Г{2*) = Г(2*-1) + 2*,

решением которого, очевидно, служит Г(2*)=2*+1-1.

Таким образом, с помощью расстановки последовательность из п операций ВСТАВИТЬ, ПРИНАДЛЕЖАТЬ и УДАЛИТЬ можно выполнить за среднее время 0{п).

Здесь важен выбор функции расстановки h. Если элементы, добавляемые в S, представлены целыми числами, равномерно распределенными между О и некоторым числом ф-п, то в качестве h{a)



4.3. ДВОИЧНЫЙ ПОИСК

можно взять а mod т, где т - размер таблицы расстановки в данный момент. Другие примеры функций расстановки приведены в работах, упоминаемых в конце главы.

4.3. ДВОИЧНЫЙ ПОИСК

в данном разделе сравниваются три различных решения одной простой задачи поиска. Дано множество S из п элементов, взятых из большого универсального множества. Требуется выполнить последовательность а, состоящую только из операций ПРИНАДЛЕЖАТЬ.

Наиболее прямым путем решения было бы запомнить элементы множества S в некотором списке. Каждая операция ПРИНАДЛЕЖАТЬ (а, S) выполняется последовательными просмотрами этого списка до тех пор, пока не найдется данный элемент а или не будут просмотрены все элементы списка. Выполнение всех операций из о заняло бы тогда время порядка пХ а как в худшем случае, так и в среднем. Основное преимущество этой схемы в том, что предварительная работа здесь занимает очень мало времени.

Другой путь - разместить элементы множества S в таблице расстановки размера S. Операция ПРИНАДЛЕЖАТЬ (а, S) выполняется поиском в списке/i (а). Если можно найти хорошую функцию h, то выполнение а займет время О(0) в среднем и 0{п\а\) в худшем случае. Основная трудность здесь связана с нахождением функции расстановки, равномерно распределяющей элементы из S в таблице расстановки.

Если на S задан линейный порядок то третьим решением будет двоичный поиск. Элементы из S хранятся в массиве А. Этот массив упорядочивается так, чтобы было Л[1]< Л[2]< ... <.А[п]. Теперь, чтобы установить, принадлежит ли элемент а множеству S, надо сравнить его с элементом Ь, который хранится в ячейке [ [Ц-/г)/2 J. Если а=Ь, то остановиться и ответить "да". В противном случае повторить эту процедуру на первой половине массива, если а<.Ь, и на второй, если а>Ь. Повторно разбивая область поиска пополам, можно не более чем за f log {п+1) ~\ сравнений либо найти а, либо установить, что его нет в S.

Рекурсивная процедура ПОИСК (а, /, /), приведенная на рис. 4.3, ищет элемент а в ячейках /, /+1, /+2, . . ., / массива А. Для установления принадлежности а множеству S вызывается ПОИСК (а, 1, п).

Чтобы понять, почему эта процедура работает, представим массив А в виде двоичного дерева. Корень находится в ячейке (1+п)/2 J , а его левый и правый сыновья - в ячейках [ (1+га)/4 J и 3(1+п)/4 J соответственно, и т. д. Эта интерпретация двоичного поиска станет яснее в следующем разделе.



1) Разумеется, поскольку в расстановке участвуют не только сравнения, то, возможно, она окажется лучше двоичного поиска; во многих случаях это действительно так.

procedure ПОИСК(а, /, /): if / > / then return "нет" else

if a=A[i(f + l)/2J] then return "да" else

if a<A[l(f + l)/2J] then

return ПОИСК(а, /, i{f + l)/2J-1) else return ПОИСК(а, i{f + l)/2J +1, I)

Рис. 4.3. Процедура двоичного поиска.

Легко показать, что на розыск элемента в А ПОИСК тратит не более f log (n+1) "J сравнений, так как никакой путь в рассматриваемом дереве не длиннее f log(«+l) ~\. Если все элементы как цели для поиска равновероятны, то можно также показать (упр. 4.4), что ПОИСК дает оптимальное среднее число сравнений (а именно, ologn), необходимое для выполнения операций ПРИНАДЛЕЖАТЬ в последовательности а»).

4.4. ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА

Рассмотрим следующую задачу. В множество S вставляются и из него удаляются элементы. Время от времени нам может понадобиться узнать, принадлежит ли данный элемент множеству S или, например, каков в данный момент наименьший элемент в 5. Мы считаем, что элементы добавляются в 5 из большого универсального множества, линейно упорядоченного отношением <. Эту задачу можно сформулировать в общем виде как выполнение последовательности, состоящей из операций ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЬ и M1N.

Мы уже видели, что для выполнения последовательности операций ВСТАВИТЬ, УДАЛИТЬ и ПРИНАДЛЕЖАТЬ хорошей структурой данных может служить таблица расстановки. Но нельзя найти наименьший элемент, не просмотрев всю таблицу. Структурой данных, пригодной для всех четырех операций, является дерево двоичного поиска.

Определение. Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l{v)S так, что





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 [41] 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021