If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Análise da busca em largura

Quanto tempo a busca em largura leva para um gráfico de vértice definido como V e borda definida como E? A resposta é O(V+E) de tempo.
Vamos ver o que O(V+E) de tempo significa. Assuma que |E||V|, que é o caso para a maioria dos gráficos especialmente os que vamos executar a busca em largura. Então |V|+|E||E|+|E|=2|E|. Porque nós ignoramos fatores constantes na notação assintótica, vemos que quando |E||V|, O(V+E) significa realmente O(E). Se, no entanto, nós temos |E|<|V|, então |V|+|E||V|+|V|=2|V|, e então O(V+E) realmente significa O(V). Nós podemos colocar os dois casos juntos dizendo que O(V+E) realmente significa O(max(V,E)). Em geral, se nós temos parâmetros x e y, então O(x+y) realmente significa O(max(x,y)).
(A propósito, note que um gráfico é ligado se há um caminho que conecta todos os vértices. O número mínimo de arestas que um gráfico pode ter e ainda estar ligado é |V|1. Um gráfico no qual |E|=|V|1 é chamado de árvore sem raiz.)
Como essa busca em largura é executada O(V+E)? Ela demora O(V) de tempo para iniciar a distância e o prdecessor para cada vértice (Θ(V) de tempo, na verdade). Cada vértice é visitado no máximo uma vez, porque só na primeira vez que a distância é alcançada null, e então cada vértice é enfileirado no máximo uma vez. Desde que nós examinamos o incidente de bordas em um vértice somente quando visitamos, cada aresta é examinada no máximo duas vezes, já que para a maioria das vezes o vértice sobre. Então, a pesquisa de amplitude gasta O(V+E) de tempo para visitar os vértices.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.