Представьте себе следующий граф (это не реальный граф), верхний уровень которого представляет ациклический ориентированный граф с узлами n, а нижний уровень представляет ациклический ориентированный граф с узлами m. Каждый узел на верхнем уровне связан с несколькими узлами на нижнем уровне (скажем, каждый узел на верхнем уровне покрывает несколько узлов на нижнем уровне). Таким образом, n меньше m (каждый узел на верхнем уровне, по крайней мере, охватывает 2 узла на нижнем уровне).
Мои вопросы:
1- Каковы временные и пространственные сложности, использующие алгоритм depth-first search для поиска всех последовательностей из определенного узла на верхнем уровне и на нижнем уровне? и как эти временные и пространственные сложности двух уровней можно сравнить (как они связаны)?
Мой ответ о сложности времени и пространства, о котором я подозреваю, следующий:
- Верхний уровень: сложность времени: o (n), сложность пространства: o (n + e) (e:
количество ребер).
- Нижний уровень: сложность времени: o (m), сложность пространства: o (m + e) (e: количество ребер).
Но я не могу найти отношения между этими двумя.
2- Если мы хотим найти все возможные последовательности из одного узла на нижнем уровне графика, если к этому графику будет добавлен дополнительный узел, как увеличится количество последовательностей (для сценария наихудшего случая)?
Любая идея приветствуется!