Logo Passei Direto
Buscar

Estrutura de Dados

Outros
Se um algoritmo tem complexidade (n log n) no melhor caso, o que isso significa?
a) Ele nunca executa mais rapido que n log n para entradas grandes.
b) Ele sempre executa exatamente em n log n operacoes.
c) Ele pode executar em tempo constante no melhor caso.
d) Ele possui complexidade O(n log n) no pior caso.
User badge image
Aprimorando com Questões

há 4 meses

User badge image
Aprimorando com Questões

há 4 meses

Big Omega
7 pág.

Big Omega

CEFET/RJ

Respostas

User badge image

Ed Verified user icon

há 4 meses

Vamos analisar as alternativas em relação à complexidade (n log n) no melhor caso de um algoritmo: a) Ele nunca executa mais rápido que n log n para entradas grandes. - Esta afirmação não é verdadeira, pois a complexidade no melhor caso indica que, em algumas situações, o algoritmo pode ser mais rápido. b) Ele sempre executa exatamente em n log n operações. - Isso também não é correto, pois a complexidade no melhor caso não significa que o algoritmo sempre executa exatamente esse número de operações. c) Ele pode executar em tempo constante no melhor caso. - Esta opção é plausível, pois um algoritmo pode ter um desempenho melhor em casos específicos, podendo até mesmo ser constante. d) Ele possui complexidade O(n log n) no pior caso. - Esta afirmação não é necessariamente verdadeira, pois a complexidade no melhor caso não implica na complexidade do pior caso. Dentre as opções, a mais correta é: c) Ele pode executar em tempo constante no melhor caso.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

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

Essa pergunta também está no material:

Big Omega
7 pág.

Big Omega

CEFET/RJ

Mais perguntas desse material

Qual e a definicao formal de Big Omega () em analise de algoritmos?
a) E uma funcao que descreve o pior caso de um algoritmo.
b) E uma funcao que descreve o melhor caso de um algoritmo.
c) E uma funcao que descreve o crescimento assintotico inferior de um algoritmo.
d) E uma funcao que descreve o tempo medio de execucao de um algoritmo.

Qual das seguintes expressoes representa corretamente que uma funcao f(n) e (g(n))?
a) Existem constantes c > 0 e n0 1 tal que 0 f(n) c·g(n) para todo n n0
b) Existem constantes c > 0 e n0 1 tal que 0 c·g(n) f(n) para todo n n0
c) f(n) = O(g(n))
d) f(n) = (g(n))

Considerando o algoritmo de busca linear em um vetor de n elementos,
qual seria a notacao Big Omega para seu caso melhor?
a) (1)
b) (n)
c) (log n)
d) (n2)

Suponha que um algoritmo execute exatamente n2 + 5n + 3 operacoes para um dado tamanho de entrada n. Qual e a complexidade assintotica inferior usando Big Omega?
a) (n)
b) (n2)
c) (n3)
d) (log n)

Qual das afirmativas sobre Big Omega e verdadeira?
a) (f(n)) fornece um limite superior de desempenho.
b) (f(n)) sempre indica o tempo exato de execucao do algoritmo.
c) (f(n)) fornece um limite inferior, garantindo que o algoritmo nunca sera mais rapido que esse limite para entradas grandes.
d) (f(n)) nao possui relacao com Big O ou .

Qual seria a notacao Big Omega para a funcao f(n) = 3n3 + 7n2 + 2n + 1?
a) (n)
b) (n2)
c) (n3)
d) (log n)

Qual e a relacao entre as notacoes Big O, Big Omega e Big Theta?
a) Big O e limite inferior, Big Omega e limite superior, Big Theta e exato.
b) Big O e limite superior, Big Omega e limite inferior, Big Theta representa limite assintotico exato.
c) Big O e Big Omega sao equivalentes, Big Theta e diferente.
d) Nao ha relacao entre essas notacoes.

Se f(n) = (g(n)), e correto afirmar que g(n) = O(f(n))?
a) Sim, sempre.
b) Nao, nunca.
c) Somente se f(n) = (g(n)).
d) Somente se f(n) for constante.

Para um algoritmo de ordenacao por selecao, qual seria a notacao Big Omega no melhor caso?
a) (1)
b) (n)
c) (n2)
d) (log n)

Mais conteúdos dessa disciplina