Logo Passei Direto
Buscar

Qual é a complexidade de tempo do algoritmo de Dijkstra ao utilizar um heap binário? a) O(V^2) b) O(V + E) c) O((V + E) log V) d) O(E)

User badge image
Aprendendo Através de Exercícios

há 2 anos

Respostas

User badge image

Ed Verified user icon

há 2 anos

Para determinar a complexidade de tempo do algoritmo de Dijkstra utilizando um heap binário, vamos analisar as operações principais: 1. Extração do mínimo: Essa operação, que é feita a partir do heap, tem complexidade O(log V). 2. Relaxamento das arestas: Para cada aresta, pode ser necessário atualizar a distância, o que ocorre em O(1) para cada aresta. Assim, considerando que o algoritmo percorre todos os vértices (V) e todas as arestas (E), a complexidade total se torna: - Extração do mínimo: O(V log V) - Relaxamento das arestas: O(E) Portanto, a complexidade total é O((V + E) log V). Assim, a alternativa correta é: c) O((V + E) log V).

Essa resposta te ajudou?

0
Dislike0

Ainda não achou a resposta?

  • Integrado com os principais modelos de IA do mercado
  • Respostas em segundos
  • IA treinada para estudantes brasileiros.
PasseIA logoEvolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Mais perguntas desse material

Mais conteúdos dessa disciplina