Изменения

Перейти к: навигация, поиск

Pintreepi1Lmax

2 байта добавлено, 16:20, 30 мая 2016
Асимптотика
==== Асимптотика ====
# На перов первом шаге мы посещаем каждую вершину ровно два раза (первый {{---}} когда ищем вершину без родителя, второй {{---}} когда релаксируем дедлайны) за <tex>O(n)</tex> времени.
# Делаем сортировку вершин за <tex>O(n \log n)</tex>, а затем для каждой вершины считаем время за линейное время.
Итоговая сложность {{---}} <tex>O(n \log n)</tex>
317
правок

Навигация