Мат. ожидание высоты бинарного дерева - Алгоритмы

Алгоритмы

Форум программистов и сисадминов Киберфорум

Войти

Регистрация
Восстановить пароль

@OOORKHAN 0 / 0 / 1 Регистрация: 11.06.2018 Сообщений: 20
		1
	Мат. ожидание высоты бинарного дерева 01.06.2021, 01:05. Показов 1021. Ответов 0 Метки алгоритм, алгоритмы, бинарное дерево, дискретная математика, доказательство, комбинаторика, математическое ожидание, теория вероятностей (Все метки) Вот есть такая теорема: мат. ожидание высоты случайного бинарного дерева поиска с n ключами равна O(logn). И в этой теореме говорят, что пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?X_n$ - высота этого бинарного дерева, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?Y_n = 2^{X_n}$ - его экспоненциальная высота. С помощью некоторых преобразований получается, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?E[Y_n] \leq \frac{4}{n}\sum\limits_{i=0}^n E[Y_i]$ . И потом говорят, что данное неравенство имеет следующее решение для всех натуральных n: $https://www.cyberforum.ru/cgi-bin/latex.cgi?E[Y_n] \leq \frac{1}{4}\frac{(n+3)!}{3!n!}$ . Дальше показывается, что это верно для $https://www.cyberforum.ru/cgi-bin/latex.cgi?Y_0 = 0 = E[Y_0]$ и для $https://www.cyberforum.ru/cgi-bin/latex.cgi?Y_1 = 1 = E[Y_1]$ . Но не ясно, откуда вообще взялось это решение с факториалами? Как эту формулу можно именно вывести, а не доказывать по индукции ее справедливость? Заранее спасибо! 0

Заказать работу у эксперта

Programming

Эксперт

94731 / 64177 / 26122

Регистрация: 12.04.2006

Сообщений: 116,782

01.06.2021, 01:05

Ответы с готовыми решениями:

Теорема о мат ожидании высоты бинарного дерева
Вот есть теорема о том, что мат ожидание высоты бинарного дерева с n ключами - O(log n). И вот в...

Вычисление высоты бинарного дерева
Разработать программу вычисления высоты дерева(бинарного дерева) Очень прошу напишите эту задачу...

Определение высоты бинарного дерева
Помогите разобраться с кодом, нашел алгоритм быстрого определения высоты бинарного дерева: int...

Функция: определение высоты бинарного дерева
написать функцию , которая определяет высоту бинарного дерева

	01.06.2021, 01:05

IT_Exp

Эксперт

87844 / 49110 / 22898

Регистрация: 17.06.2006

Сообщений: 92,604

01.06.2021, 01:05

Помогаю со студенческими работами здесь

Вычисление высоты бинарного дерева поиска на С++
Никак не могу вывести нормально высоту дерева, уже второй день маюсь, подскажите пожалуйста, в чем...

Формирование бинарного дерева и нахождение его высоты
Не знаю правильно ли работает программа. Вроде бы что-то не то с вводом дерева. Посмотрите плиз,...

Определение высоты каждой пары элементов данного бинарного дерева
определения высоты каждой пары элементов данного бинарного дерева

Найти путь максимальной длины между вершинами разной высоты бинарного дерева
Я уже задавал аналогичный вопрос в другом разделе форума, но там просмотров меньше чем в этом...

Реализовать класс, задающий конструкцию "бинарное дерево" и функцию вычисления высоты бинарного дерева
Выручайте, через 2 часа сдавать лабу... Суть самой лабы ниже... Реализовать класс, задающий...

Мат ожидание . Нер-ва связанные с мат ожиданием
Подскажите, пожалуйста, через какие формулы можно вывести доказательство

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Наверх