Logo Passei Direto
Buscar

Cálculo Numérico

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

a) O(n)
b) O(n^2)
c) O(n^3)
d) O(n log n)
User badge image
Questões Para a Compreensão

há 2 anos

User badge image
Questões Para a Compreensão

há 2 anos

simples csh
3 pág.

simples csh

UNIP

Respostas

User badge image

Ed Verified user icon

há 2 anos

O algoritmo de Floyd-Warshall é um algoritmo clássico utilizado para encontrar todos os caminhos mais curtos entre todos os pares de vértices em um grafo. A complexidade de tempo desse algoritmo é determinada pelo número de vértices no grafo e pelas operações que ele realiza. O algoritmo realiza três laços aninhados, cada um iterando sobre todos os vértices do grafo. Portanto, a complexidade de tempo do algoritmo de Floyd-Warshall é O(n^3), onde n é o número de vértices. Analisando as alternativas: a) O(n) - Incorreto. b) O(n^2) - Incorreto. c) O(n^3) - Correto. d) O(n log n) - Incorreto. Portanto, a resposta correta é: c) O(n^3).

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 csh
3 pág.

simples csh

UNIP

Mais perguntas desse material

Um algoritmo de ordenação por seleção tem um tempo de execução em média de:

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

Qual é a complexidade de tempo do algoritmo de Dijkstra para encontrar o caminho mais curto em um grafo denso com n vértices?

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

Dado um vetor com 100 elementos, qual é o número máximo de comparações necessárias para encontrar o menor elemento usando uma busca linear?

a) 50
b) 99
c) 100
d) 101

Um problema de programação dinâmica pode ser resolvido em tempo polinomial se:

a) Ele pode ser dividido em subproblemas independentes
b) Ele pode ser dividido em subproblemas sobrepostos
c) Ele não pode ser resolvido por recursão
d) Ele não tem solução

Em um problema de otimização, se a função objetivo é não linear, qual método pode ser usado para encontrar a solução?

a) Programação Linear
b) Programação Dinâmica
c) Algoritmos Genéticos
d) Busca Binária

Um algoritmo de força bruta para resolver um problema de combinação de 10 elementos tem complexidade de tempo de:

a) O(10)
b) O(10!)
c) O(2^10)
d) O(10^2)

Qual é a complexidade de tempo do algoritmo de Kruskal para encontrar a árvore geradora mínima em um grafo?

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

Mais conteúdos dessa disciplina