#graph #time-complexity #shortest-path
#График #временная сложность #кратчайший путь
Вопрос:
Учитывая, что ориентированный ациклический граф со степенью ‘d’ и длиной кратчайшего пути между любыми двумя узлами равен ‘n’, сколько времени требуется, чтобы найти этот путь в терминах d и n?
Ответ №1:
Если вы говорите о конкретном пути между двумя узлами x и y: это O (d ^ n), как и в любом узле, в пути, вы должны «брать» до d разных путей. И вам придется повторять этот процесс до n раз.
Поскольку она экспоненциальна в n, этот анализ времени полезен только для очень маленьких n. В основном, вы предпочтете рассматривать это как запуск DFS на вашем графике, что приводит к O (E V) (этот размер вашего графика)
Комментарии:
1. Я думаю, мы можем рассматривать это как дерево, где каждый узел имеет не более d дочерних элементов, тогда количество узлов было бы d ^ n, и нам пришлось бы искать эти узлы, поэтому временная сложность должна быть O (d ^ n). Поправьте меня, если я где-то ошибаюсь.