2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Высота в декартовом дереве с случайными приоритетами
Сообщение11.02.2021, 10:32 


14/07/16
57
Здравствуйте, пытаюсь разобраться в доказательстве того, что средняя глубина вершины в декартовом дереве есть $O(\log n)$.
Не могу понять следующий момент: в доказательстве предполагается что все приоритеты вершин различны, и приоритеты равномерно распределены. Тогда вероятность того что среди $k$ вершин, первая вершина будет иметь максимальный приоритет равна $\frac{1}{k}$. С одной стороны, для случаев $k = 1, 2$ это кажется очевидным. Но вот для случаев $k > 2$ не очень понимаю как доказывать. Подскажите пожалуйста.

 Профиль  
                  
 
 Re: Высота в декартовом дереве с случайными приоритетами
Сообщение20.02.2021, 21:20 


27/01/16
86
Не знаю, правильно ли я вас понял, но если ведь очевидно, что из $k$ одинаково распределенных величин какая то одна конкретная будет максимальной с вероятностью $\frac{1}{k}$
Таким образом расставя их случайно по вершинам , шанс того что в корне будет максимальная и равен $\frac{1}{k}$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group