264
правки
Изменения
м
→Время работы
|id=deglemma
|proof=
Воспользуемся регрессионным анализом, и, вместо того, чтобы считать, сколько вершин удет соединено с вершиной после ее вставки, расмотрим количество вершин, которые потеряют соседа после ее удаления.
Рассмотрим функцию <tex>\sigma(p_i, p_j) </tex>, которая равна единице, если вершины <tex>p_i</tex> и <tex>p_j</tex> соединены и нулю иначе.
<tex>\dfrac{\sum \limits_{p_i} \sum\limits_{p_j} \sigma(p_i, p_j) }{\left| P \right|} = \dfrac{\sum \limits_{p_i} 6 }{\left| P \right|} = =O(1) </tex>
Предположим, что мы вставляем <tex>i+1</tex>-ую точку из последовательности из <tex>n</tex> точек. Рассмотрим все перестановки из этих <tex>i+1</tex> точек, означающие порядок вставки этих точек. Всего таких перестановок <tex>(i+1)!</tex>. Тогда средняя степень последней вершины среди перестановок равна:
