Решение pекуppентных соотношений

⇐ ПредыдущаяСтр 2 из 2

где n = M, M+1, M+2, ..., М - известная постоянная, имеет вид

В моногpафии Д.Кнута [3, с.107-110] числа H_n назваются гаpмоническими числами.

Доказательство леммы.

Из соотношения (1) легко можно получить

Вычитая, получим

где x₀ - известная постоянная.

Для дальнейшего упрощения формулы (2) положим

f_n = a*n + b, (3)

где a и b - известные постоянные.

ЛЕММА ДОКАЗАНА.

Доказательство теоpемы.

Пусть T_n - число сравнений, производимых между элементами последовательности a₁, a₂, a₃, ..., a_n пpи построении бинарного дерева поиска, T_o= 0.

Пусть b₁, b₂, b₃, ..., b_n - та же последовательность в порядке возрастания. Если a₁, a₂, a₃, ..., a_n - случайная последовательность элементов, то a₁ с равной вероятностью совпадает с b_j для любого j, 1 <= j <= n.

Элемент a₁ становится корнем бинарного дерева поиска, и в окончательном деpеве j-1 элементов b₁, b₂, ..., b_j-1 будут находиться в левом поддереве корня и n-j элементов b_j+1, b_j+2, ..., b_n - в правом поддереве.

Подсчитаем среднее число сравнений, необходимых для вставки элементов b₁, b₂, ..., b_j-1 в дерево. Каждый из этих элементов когда-нибудь сравнивается с корнем, и это дает j-1 сравнений с корнем. Затем по индукции получаем, что еще потребуется T_j-1 сравнений, чтобы вставить b₁, b₂,...,b_j-1 в левое поддерево.

Итак, необходимо j-1 + T_j-1 сравнений, чтобы вставить b₁, b₂, ..., b_j-1 в бинарное дерево поиска. Аналогично n-j + T_n-j сравнений потребуется, чтобы вставить в дерево элементы b_j+1, b_j+2, ..., b_n.

Поскольку j с равной вероятностью принимает любое значение от 1 до n, то

Применим результаты доказанной ранее леммы: так как a=1, b= -1, T_o=0, то T_n = 2(n+1)H_n- 4n .

Таким образом, в среднем на вставку n элементов в дерево двоичного поиска тратится в среднем O(nlog₂n) сравнений.

ТЕОРЕМА ДОКАЗАНА .

ЗАДАНИЕ:

1) Осуществить изучение материала путем реализации приведенных примеров кода.

2) Провести разбор доказательства Теоpема Хопкpофта-Ульмана (данный вопрос выносится на экзамен)

3) Ответить на следующие вопросы:

a) Что такое бинарное дерево поиска, чем оно отличается от бинарного дерева.

b) Привести примеры использования бинарного дерева поиска.

c) Оценить эффективность данного метода.

4) При какой входной последовательности к приведенному алгоритму мы получим бинарное (двоичное) дерево поиска следующего вида:

Источники:

1) [ЭЛЕКТРОННЫЙ РЕСУРС]: Кафедра ПОАС КГУ; режим доступа: http://it.kgsu.ru/).

2) [ЭЛЕКТРОННЫЙ РЕСУРС]: Wikipedia; режим доступа: https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0

3) Кнут Д. Искусство программирования для ЭВМ. Т.1: Основные алгоритмы. - M.: Мир, 1976. - 736 с

4) (1) Вирт H. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с.

5) (2) Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. - 536 с.

6) (3) Кнут Д. Искусство программирования для ЭВМ. Т.1: Основные алгоритмы. - M.: Мир, 1976. - 736 с.

7) (4) Кнут Д. Искусство программирования для ЭВМ. Т.3: Сортировка и поиск. - M.: Мир, 1978. - 844 с.

8) (5) Рейнгольд Э., Hивергельт Ю., Део H. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.

Дата добавления: 2021-07-19; просмотров: 99; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!