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

5.2. Анализ времени выполнения операторов

в этом разделе мы проанализируем работу различных операторов, выполняемых над деревьями двоичного поиска. Мы покажем, что если в первоначально пустое дерево двоичного поиска вставлено п произвольных элементов, то средняя длина пути от корня до листа будет O(logra). Отсюда следует, что среднее время выполнения оператора MEMBER также будет иметь порядок O(logn).

Легко видеть, что если двоичное дерево полное (т.е. все узлы, за исключением самого нижнего уровня, имеют двух сыновей), то не существует пути, содержащего более 1 + logra узлов. Поэтому операторы MEMBER, INSERT, DELETE и DELETEMIN имеют время вьшолнения порядка O(logra). Чтобы доказать это, достаточно заметить, что все эти операторы затрачивают фиксированное время на обработку одного узла, затем рекурсивно вызывают себя для обработки сына рассматриваемого узла. Последовательность узлов, в которых выполняется рекурсивный вызов процедур, формирует путь, исходящий из корня дерева. Поскольку такой путь имеет в среднем длину O(logra), то и обшее время прохождения операторами этого пути будет иметь такой же порядок.

Однако когда элементы вставляются в произвольном порядке, они не обязаны располагаться в виде полного двоичного дерева. Например, если вставка начата с наименьшего элемента и далее элементы вставляются в порядке возрастания, то получим дерево в виде цепочки узлов, где каждый узел имеет правого сына, но не имеет левого. В этом случае, как легко показать, на вставку i-ro элемента требуется 0(i) шагов, для завершения всего процесса вставки га элементов необходимо У. i = п{п + 1)/2 шагов, т.е. порядка О(п), или 0(га) на одно выполнение оператора вставки.

Мы должны уметь определять, когда "среднее" дерево двоичного поиска из п узлов ближе по своей структуре к полному двоичному дереву, а когда к цепочке узлов, так как в первом случае среднее время вьшолнения операторов имеет порядок O(logn), а во втором - 0(п). Если мы не знаем последовательность выполненных (или тех, которые будут выполнены в будушем) операций вставки и удаления элементов, а также свойства этих элементов (например, мы не можем всегда удалять только минимальные элементы), то естественно предположить, что анализу подлежат только пути "средней" длины на "случайных" деревьях. В частности, мы вправе предполагать, что деревья сформированы только вставкой элементов и все последовательности вставляемых элементов равновероятны на фиксированном множестве из п элементов.


Рис. 5.3. Построение дерева двоичного поиска

Принимая эти достаточно естественные предположения, можно вычислить Р{п) - среднее число узлов в пути от корня до некоторого узла (не обязательно листа). Предполагая, что дерево формируется путем вставки п произвольных элементов в

Напомним, что все логарифмы, пока не сказано другое, определены по основанию 2. 150 ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ



первоначально пустое дерево, очевидно, что Р(0) = О н Р(1) - I. Пусть в списке из п > 2 элементов, готовых к вставке в пустое дерево, первым находится элемент а. Если отсортировать список, то элемент а с равной вероятностью может занимать любое место от 1 до п. Пусть в списке i элементов меньше а, и, следовательно, п - i - 1 элементов больше, чем а. Тогда при построении дерева в его корне поместится элемент а (поскольку он первый элемент списка), i наименьших элементов будут потомками левого сына корня, а оставшиеся п - i - 1 элементов - потомками правого сына корня. Это дерево показано на рис. 5.3.

Так как любые последовательности i наименьших элементов н п - i - 1 наибольших элементов равновероятны, мы вправе предположить, что средняя длина путей в левом и правом поддеревьях будет P(i) я Р(п - i - 1) соответственно. Поскольку пути должны начинаться от корня полного дерева, то к P(i) и Р(п - i - 1) надо еше прибавить 1. Тогда Р(п) можно вычислить путем усреднения для всех г от О до и - 1 следующих сумм:

-(Р(0+ 1)+"~~\р(/ь/ - 1)+ 1)-Ь -,

ИИ и

где первое слагаемое - средняя длина пути в левом поддереве с весовым коэффициентом i/n, значение второго слагаемого аналогично, а 1/га соответствует "вкладу" в путь корня. Усредняя эти выражения по всем i от О до и - 1, получим рекуррентное уравнение

Р(га)= 1 (ra-i-l)P(ra-/- 1)). (5.1)

л 1=0

Вторая часть этой суммы ""J (га - i - 1)Р(га-г - 1) , если подставить i вместо

(п - i - 1), преобразуется в первую часть (5.1) ""iPO) В последней сумме слагаемое при 1 = 0 равно нулю, поэтому суммирование можно начинать с i = 1. Таким образом, формулу (5.1) можно переписать в следующем виде:

P(ra)=l+4l(i), п>2. (5.2)

Теперь индукцией по п покажем, что Р(п) < 1 -i- 41ogra. Очевидно, что это утверждение справедливо для и = 1, поскольку Р(1) = 1, и для п = 2, так как Р(2) = 2 < 1 -i- 41og2 = 5. Предположим, что оно выполняется для всех i < п. Тогда на основании (5.2) имеем

P(n)<l + 4S(tl<g + 0=l + 4Xil°g+4S 2 + (5.3)

п п j i п , 1 га ii"

Здесь использовано неравенство У""»<га2, поэтому - Разделим

последнюю сумму в (5.3) на две суммы: по i < [га/2], в этом случае слагаемые не будут превышать ilog(n/2), и по i > [га/2], где слагаемые не превышают tlog(n). Тогда неравенство (5.3) можно переписать так:

Р(п)<2+4- yilog(ra/2)+ У tlogn\ (5.4)

Независимо от того, четное или нечетное га, нетрудно показать, что первая сумма в (5.4) не превышает величины (ra/8)log(ra/2), которая равна (ra/8)Iogra - (га/8), а вторая не превышает (3n/8)logn. С учетом этих оценок из (5.4) получаем

Р(п)<2-Ь -

-logn--

< И- 41ogra.

Этот шаг завершает индукцию и доказывает утверадение. Итак, доказано, что в дереве двоичного поиска, которое получено путем случайной вставки га элементов, средняя

5.2. АНАЛИЗ ВРЕМЕНИ ВЫПОЛНЕНИЯ ОПЕРАТОРОВ 151



длина пути от корня до произвольного узла имеет порядок O(logn), т.е. точно такой же порядок (с точностью до константы пропорциональности), как и для полного двоичного дерева. Более точный анализ показывает, что константу 4 в вышеприведенной оценке можно заменить на 1.4.

Из доказанного утверждения следует, что время выполнения проверки на принадлежность произвольного элемента к множеству имеет порядок O(logra). Подобный анализ показывает, что если мы включим в путь только те узлы, которые имеют обоих сыновей, или только узлы, имеюшие лишь левого сына, то все равно для средней длины пути подучим уравнение, подобное (5.1), и поэтому будет оценка порядка O(logra). Отсюда следует вывод, что для выполнения операций проверки на принадлежность к множеству элемента, которого заведомо нет в множестве, вставки произвольного нового элемента или удаления элемента также требуется в среднем времени порядка O(logra).

Эффективностьдеревьевдвоичного поиска

При реализации словарей посредством хеш-таблиц время выполнения основных операторов в среднем постоянно, т.е. практически не зависит от размера множеств. Поэтому такая реализация более эффективна, чем реализация деревьев двоичного поиска, за исключением того случая, когда необходимо часто применять оператор MIN, который требует времени порядка 0(п) для хеш-таблиц.

Сравним деревья двоичного поиска с частично упорядоченными деревьями, которые применяются для реализации очередей с приоритетами (см. главу 4). Частично упорядоченные деревья из п элементов требуют только O(logra) шагов для выполнения операторов INSERT и DELETEMIN, но не в среднем, а в самом худшем случае. Более того, константа пропорциональности перед logn для частично упорядоченных деревьев меньше, чем для деревьев двоичного поиска. Но на дереве двоичного поиска могут выполняться как операторы DELETE и MIN, так и их комбинация DELETEMIN, тогда как на частично упорядоченном дереве выполняется только последний из этих операторов. Кроме того, оператор MEMBER требует 0(п) шагов на частично упорядоченном дереве, но только O(logra) шагов на дереве двоичного поиска. Таким образом, частично упорядоченные деревья хорошо подходят для реализации очередей с приоритетами, но не эффективны при выполнении других операторов множеств, которые могут выполняться на деревьях двоичного поиска.

5.3. Нагруженные деревья

В этом разделе мы рассмотрим специальную структуру для представления множеств, состояших из символьных строк. Некоторые из описанных здесь методов могут работать и со строками объектов другого типа, например со строками целых чисел. Эта стэуктура называется нагруженными деревьями (tries). Рассмотрим их применение к символьным строкам.

В оригинале структура называется trie, это слово получено из букв, стоящих в середине слова "retrieval" (поиск, выборка, возврат). Устоявшегося термина для этой структуры в русской литературе пока нет. (О расхождении терминологии можно судить по переводу известной книги D.E. Knuth. The art of computer programming, Vol. Ill: Sorting and Searching: в первом русском переводе (Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. - М., "Мир", 1978 г.) вместо trie используется термин бор (от слова выборка), в последнем переводе переработанного издания этой книги (Кнут Д. Искусство программирования. Т. 3: Сортировка и поиск. - М., Издательский дом "Вильяме", 2000 г.) - термин луч (от слова полг/чение).) Чтобы не заниматься "терминотворчеством", мы применили известный термин нагруженные деревья, который соответствует смыслу этой структуры. В данном случае можно было бы применить и термин синтаксические деревья, но, хотя этот термин по своему значению и "пересекается" с термином нагруженные деревья, он имеет другую направленность. - Прим.ред.





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

0.004