CD
это удивительно, ведь у него линия разреза есть
Size: a a a
2021 April 21
NK
угу, там просто видимо надо аккуратно вероятностное пространство рассматривать
CD
хм... неужели я ловлюсь на парадокс про экзамен и скипать билет номер 13?
CD
типа не важно, будешь ждать ты, когда 13й билет выпадет другому студенту или пойдешь сразу - шанс не меняется
CD
вот интуиция говорит, что если удалить первый элемент массива, в дереве станет меньше левых потомков
CD
но их станет меньше только если первый элемент не корень дерева
K
Как ни странно, заметно ускорилось, если заменить приоритет с float на int
NK
ну тут момент что если смортреть на два дерева которые там появляются внутри алгоритма то нифига они не равномерные
NK
надо смотреть на одно конкретное
CD
если они не равномерное, то у нас всё пойдёт п*дой, но похоже, что они на самом деле равномерные
NK
ну надо смотреть на одно конкретное
NK
в отрыве от других
NK
когда с приорететами происходит доказательство там тоже надо говорить что высота каждого не может быть большой с очень большой вероятностью
NK
а потом брать тупой union bound
CD
ну вот где я туплю, когда мы удаляем первый элемент из дерева, если он не корень, то он - левый потомок предка
CD
почему в дереве после этого не стало в среднем больше правых потомков предка, чем левых?
CD
если он был лист - число левых потомков уменьшилось
если он не был лист - не изменилось
если он был корень - увеличилось
вероятность самого левого элемента быть листом это 1/N ?!
если он не был лист - не изменилось
если он был корень - увеличилось
вероятность самого левого элемента быть листом это 1/N ?!
CD
а можешь прямо посчитать эту метрику? количество не nullptr в левом и правом потомке дерева, высплитывая и выкидывая каждый раз первый элемент
K
не понял, что за метрика
K
но если применять только к первому элементу, всё летает