Как анализировать сложность времени DAG?

Question

Я изучаю топологический вид и графики в целом. Я использовал версию ниже, используя DFS, но у меня возникли проблемы с пониманием того, почему на странице wikipedia указано, что это O (| V | + | E |), и анализируя ее временную сложность, а также разницу между | V | + | E | и п^2 вообще.

Во-первых, у меня есть два для циклов, логика говорит, что это будет (n^2), но также не верно, что в любом DAG (или Tree) есть n-1 ребра и n вершин? Как это отличается от n^2, если мы можем удалить «-1» для несущественного значения?

graph = { 
1:[4, 5, 7], 
2:[3,5,6], 
3:[4], 
4:[5], 
5:[6,7], 
6:[7], 
7:[] 
} 



from collections import defaultdict 

def topological_sort(graph): 
    ordered, marked = [], defaultdict(int) 

    while len(ordered) < len(graph): 
     for vertex in graph: 
      if marked[vertex]==0: 
       visit(graph, vertex, ordered, marked) 

return ordered 

def visit(graph, n, ordered, marked): 
    if marked[n] == 1: 
     raise 'Not a DAG' 

    marked[n] = 1 

    for neighbor in graph.get(n): 
     if marked[neighbor]!=2: 
      visit(graph, neighbor, ordered, marked) 

    marked[n] = 2 

    ordered.insert(0, n) 


def main(): 
print(topological_sort(graph)) 

main() 

Answer 1

Надлежащее выполнение работ в O(|V| + |E|) время, потому что она проходит через каждое ребро и каждая вершина не более одного раза. Это то же самое, что и O(|V|^2) для полного (или почти полного графика). Однако, гораздо лучше, когда график разрежен.

Вы внедряете O(|V|^2), а не O(|V| + |E|). Эти два вложенных цикла:

while len(ordered) < len(graph): 
    for vertex in graph: 
     if marked[vertex]==0: 
       visit(graph, vertex, ordered, marked) 

сделать 1 + 2 ... + |V| = O(|V|^2) итераций в самое худшее, что (например, для пустого графа). Вы можете легко исправить, избавившись от внешнего цикла (это просто: просто удалите цикл while, который вам не нужен).