Ed
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).
Cadastre-se ou realize login
Mais perguntas desse material