Logo Passei Direto
Buscar

Estrutura de Dados

Outros

Qual é a complexidade de tempo do algoritmo de Dijkstra em um grafo esparso? a) O(E) b) O(V log V) c) O(E log V) d) O(V^2)

User badge image
Desafios Para o Conhecimento

há 2 anos

User badge image
Desafios Para o Conhecimento

há 2 anos

simples chs
3 pág.

simples chs

UNIP

Respostas

User badge image

Ed Verified user icon

há 2 anos

Para determinar a complexidade de tempo do algoritmo de Dijkstra em um grafo esparso, precisamos considerar a estrutura de dados utilizada. Quando utilizamos uma fila de prioridade (como um heap), a complexidade do algoritmo se torna O(E log V), onde E é o número de arestas e V é o número de vértices. Analisando as alternativas: a) O(E) - Esta complexidade não é correta para o algoritmo de Dijkstra. b) O(V log V) - Esta complexidade não se aplica ao algoritmo de Dijkstra. c) O(E log V) - Esta é a complexidade correta para o algoritmo de Dijkstra em um grafo esparso. d) O(V^2) - Esta complexidade se aplica a uma implementação mais simples do algoritmo, mas não é a mais eficiente. Portanto, a alternativa correta é: c) O(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:

simples chs
3 pág.

simples chs

UNIP

Mais perguntas desse material

O que caracteriza um algoritmo de ordenação in-place?

a) Ele não utiliza memória adicional
b) Ele utiliza memória adicional
c) Ele é sempre eficiente
d) Ele não altera a ordem dos elementos

Qual é a complexidade de tempo do algoritmo de ShellSort?

a) O(n log n)
b) O(n^2)
c) O(n^(3/2))
d) O(log n)

O que é um grafo ponderado?

a) Um grafo que tem arestas com pesos
b) Um grafo que não possui arestas
c) Um grafo que é sempre conexo
d) Um grafo que possui ciclos

Qual é a complexidade de tempo do algoritmo de CountingSort?

a) O(n)
b) O(n log n)
c) O(n^2)
d) O(log n)

O que caracteriza um problema de programação linear?

a) A função objetivo é não linear
b) As restrições são lineares
c) O problema não tem solução
d) A solução é sempre inteira

Qual é a complexidade de tempo do algoritmo de BogoSort?

a) O(n)
b) O(n log n)
c) O(n!)
d) O(log n)

O que é um grafo acíclico?

a) Um grafo que possui ciclos
b) Um grafo que não possui ciclos
c) Um grafo que é sempre conexo
d) Um grafo que possui arestas direcionadas

O que caracteriza um problema de satisfatibilidade booleana (SAT)?

a) A resposta é um número inteiro
b) A resposta é uma lista de números
c) O objetivo é maximizar ou minimizar uma função
d) O objetivo é determinar se uma expressão booleana pode ser satisfeita

Qual é a complexidade de tempo do algoritmo de Floyd-Warshall para encontrar todos os caminhos mais curtos em um grafo?

a) O(V^2)
b) O(E log V)
c) O(V^3)
d) O(E + V)

Mais conteúdos dessa disciplina