Complexidade temporal da profundidade da primeira pesquisa [fechada]

7

Por favor, perdoe-me por fazer uma pergunta iniciante, mas sou iniciante em algoritmos e complexidades, e às vezes é difícil entender como surgiu a complexidade de um algoritmo específico.

Eu estava lendo o algoritmo DFS de Introduction to Algorithms by Cormen , e este era o algoritmo:

G        -> graph
G.V      -> set of vertices in G
u.π      -> parent vertex of vertex u
G.Adj[u] -> adjacency list of vertex u


DFS(G)
1   for each vertex u ∈ G.V
2       u.color = WHITE
3       u.π = NIL
4   time = 0
5   for each vertex u ∈ G.V
6       if u.color == WHITE
7         DFS-VISIT(G,u)

DFS-VISIT(G,u)
1   time = time + 1            // white vertex u has just been discovered
2   u.d = time
3   u.color = GRAY
4   for each v ∈ G.Adj[u]      // explore edge u
5       if v.color == WHITE
6           v.π = u
7           DFS-VISIT(G,v)
8   u.color = BLACK            // blacken u; it is finished
9   time = time + 1
10  u.f = time

Dizia então linhas 1-3e 5-7é O(V), exclusivo do tempo para executar as chamadas DFS-VISIT(). In DFS-VISIT(), linhas 4-7são O(E), porque a soma das listas de adjacência de todos os vértices é o número de arestas. E então concluiu que a complexidade total de DFS()é O(V + E).

Eu não entendo como isso aconteceu. DFS-VISIT()é chamado por dentro DFS() . Então, se as linhas 5-7de DFS()são O(V)e DFS-VISIT()são O(E), então a complexidade total de tempo não deveria DFS()ser O(VE)?

Sidharth Samant
fonte
6
Cormen é apenas o primeiro autor listado.
Yuval Filmus
11
Bem-vindo à Ciência da Computação! Sua pergunta é muito básica. Deixe-me direcioná-lo para nossas perguntas de referência, que abrangem alguns fundamentos que você parece estar perdendo em detalhes. Por favor, trabalhe com as perguntas relacionadas listadas lá, tente resolver seu problema novamente e edite para incluir suas tentativas, juntamente com os problemas específicos que você encontrou. Boa sorte!
Raphael
Você poderia citar exatamente o texto que não entende? Se literalmente diz "exclusivo do tempo para executar as chamadas para DFS-VISIT()", isso já responde à sua pergunta: "exclusivo de DFS-VISIT()" significa que o tempo indicado não inclui o tempo gasto DFS-VISIT().
David Richerby

Respostas:

8

O livro está contando o número de vezes que cada linha é executada durante toda a execução de uma chamada do DFS, em vez do número de vezes que é executado em cada chamada da sub-rotina DFS-VISIT. Talvez o exemplo mais simples a seguir deixe isso claro:

PROCEDURE A(n)
1  global = 0
2  for i from 1 to n:
3      B(i)
4  return global

PROCEDURE B(i)
1  global = global + 1

Em cada execução de A, a linha 1 de B é executada vezes, e a própria B é executada vezes. No entanto, o tempo de execução é e não .nnO(n)O(n2)

Aqui está outro exemplo, no qual uma matriz T[1n] está envolvido.

PROCEDURE COUNT(n, T[1...n]):
1  count = 0
2  index = 1
3  while index <= n:
4    ADVANCE()
5    count = count + 1
6    index = index + 1
7  return count - 1

PROCEDURE ADVANCE():
1  while index <= n and T[index] == 0:
2    index = index + 1

O procedimento COUNT conta o número de 1s na matriz de entrada T. Mesmo que ADVANCE possa ser chamado até n vezes por COUNT e, no pior dos casos, o tempo de execução de ADVANCE é O(n), as linhas 1–2 da ADVANCE são executadas no máximo n tempos e, portanto, o tempo de execução geral é O(n) ao invés de O(n2).

Yuval Filmus
fonte
Ainda não consigo entender. A complexidade de tempo para B()é O(1), portanto, se ifor chamada de 1 to n, então será n-times O(1)-> O(n). Você diz que a linha 1 de B é executada n vezes e a própria B é executada n vezes, mas elas não são a mesma coisa?
Sidharth Samant
Eles são a mesma coisa neste exemplo, mas não no caso do DFS.
Yuval Filmus
11
Adicionei outro exemplo que é mais semelhante ao que acontece no DFS.
Yuval Filmus
Yuval senhor @ eu tenho uma dúvida.No seu algoritmo de exemplo fornecido, e se A é chamado n tempos que implica O(n2).sir por favor me ajude!
Laura
11
Executando um Θ(f(n)) procedimento g(n) vezes leva tempo Θ(f(n)g(n)).
Yuval Filmus