MO417 - Questão para a prova oral

Número: 094

Enunciado:
O tempo de execução do algoritmo de Dijkstra depende de como é implementada sua fila de prioridades. Denote por A(V,E), B(V,E) e F(V,E) o tempo de pior caso gasto pelo algoritmo em grafos de V vértices e E arestas, quando usamos respectivamente array, heap binário mínimo e heap de Fibonacci para implementar esta fila. Qual das alternativas está correta?

1. Se E = Θ(V²), então A(V,E) = o(B(V,E))
2. Se E = Θ(V²), então F(V,E) = o(A(V,E))
3. Se E = Θ(V lg V), então F(V,E) = Θ(B(V,E))
4. Se E = Θ(V), então A(V,E) = O(B(V,E))
5. NDA

Autor(a): Alisson Pontes