Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

р3 — вероятность того, что аргумент поиска key = к3
q0 — вероятность того, что key < к1
q1 — вероятность того, что к2 > key > к1
q2 — вероятность того, что к3 > key > к2
q3 — вероятность того, что key > к3
C1 — число сравнений в первом дереве рисунка 5.6 a)
C2 — число сравнений во втором дереве рисунка 5.6 б)

Тогда *р1+*р2+*р3+*q0+*q1+*q2+*q3 = 1
Ожидаемое число сравнений в некотором поиске есть сумма произведений вероятности того, что данный аргумент имеет некоторое заданное значение, на число сравнений, необходимых для извлечения этого значения, где сумма берется по всем возможным значениям аргумента поиска. Поэтому

C1 = 2*р1+1*р2+2*р3+2*q0+2*q1+2*q2+2*q3
C2 = 2*р1+3*р2+1*р3+2*q0+3*q1+3*q2+1*q3

Это ожидаемое число сравнений может быть использовано как некоторая мера того, насколько «хорошо» конкретное дерево бинарного поиска подходит для некоторого данного множества ключей и некоторого заданного множества вероятностей. Так, для вероятностей, приведенных далее слева, дерево из a) является более эффективным, а для вероятностей, приведенных справа, дерево из б) является более эффективным:
P1 = 0.1                         P1 = 0.1
P2 = 0.3                         P2 = 0.1
P3 = 0.1                         P3 = 0.3
q0 = 0.1                         q0 = 0.1
q1 = 0.2                         q1 = 0.1
q2 = 0.1                         q2 = 0.1
q3 = 0.1                         q3 = 0.2
C1 = 1.7                        C1 = 1.9
C2 = 2.4                        C2 = 1.8
Дерево бинарного поиска, которое минимизирует ожидаемое число сравнений некоторого заданного множества ключей и вероятностей, называется оптимальным. Хотя алгоритм создания дерева может быть очень трудоемким, дерево, которое он создает, будет работать эффективно во всех последующих поисках. К сожалению, однако, заранее вероятности аргументов поиска редко известны.

5.6  Бинарный поиск (метод деления пополам)

Будем предполагать, что имеем упорядоченный по возрастанию массив чисел. Основная идея — выбрать случайно некоторый элемент AM и сравнить его с аргументом поиска Х. Если AM=Х, то поиск закончен; если AM <X, то мы заключаем, что все элементы с индексами, меньшими или равными М, можно исключить из дальнейшего поиска. Аналогично, если AM >X.
Выбор М совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача- исключить как можно больше элементов из дальнейшего поиска. Оптимальным решением будет выбор среднего элемента, т.е. середины массива.

Страницы: 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

Категория: Учебники