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