Grátis: Se f é uma função de complexidade para um algoritmo F, então, O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algor... – Questões Respondidas

Estrutura de Dados

Outros

Se f é uma função de complexidade para um algoritmo F, então, O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algoritmo F. Assinale a alternativa que apresenta somente algoritmos com complexidade assintótica, quando f(n) = O(n log n):
Insertion sort.
Bubble sort.
Quick sort e merge sort.
Merge sort e bubble sort.
Quick sort e insertion sort.

Praticando Para Aprender

há 7 meses

Praticando Para Aprender

há 7 meses

Complexidade de Algoritimos AV1 - nota 10

Complexidade de Algoritimos AV1 - nota 10

ESTÁCIO

Respostas

Ed

há 7 meses

Vamos analisar as alternativas apresentadas em relação à complexidade assintótica \( O(n \log n) \): 1. Insertion sort: Este algoritmo tem complexidade \( O(n^2) \) no pior caso, portanto não se encaixa em \( O(n \log n) \). 2. Bubble sort: Assim como o Insertion sort, o Bubble sort também tem complexidade \( O(n^2) \) no pior caso, não se encaixando em \( O(n \log n) \). 3. Quick sort e merge sort: Ambos têm complexidade média de \( O(n \log n) \). Portanto, esta alternativa está correta. 4. Merge sort e bubble sort: O Merge sort é \( O(n \log n) \), mas o Bubble sort não se encaixa, então esta alternativa não é correta. 5. Quick sort e insertion sort: O Quick sort é \( O(n \log n) \), mas o Insertion sort não se encaixa, então esta alternativa também não é correta. Dessa forma, a alternativa que apresenta somente algoritmos com complexidade assintótica \( O(n \log n) \) é: Quick sort e merge sort.

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

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

Essa pergunta também está no material:

Complexidade de Algoritimos AV1 - nota 10

Complexidade de Algoritimos AV1 - nota 10

ESTÁCIO

Mais perguntas desse material

Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em um vetor de elementos. Após a completa inserção de todos os elementos neste vetor, são feitas buscas de números na mesma. O tempo médio de busca de um número neste elemento é:
O(N²)
O(N)
O(log N)
O(1)
O(Nlog N)

Analise o custo computacional dos algoritmos a seguir, que calculam o valor de polinomio de grau n da forma onde os coeficientes são números de ponto flutuante armazenados no vetor [a..n], e o valor de n é maior que zero. Todos os coeficientes podem assumir qualquer valor, exceto o coeficiente a_n que é diferente de zero. Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas. 1. Os algoritmos possuem a mesma complexidade assintótica PORQUE 1. Para o melhor caso, ambos possuem a complexidade O(n) A respeito dessas asserções, assinale a opção correta:
a primeira asserção é uma proposição verdadeira e a segunda uma proposição falsa.
as duas asserções são proposições verdadeiras e a segunda não é a justificativa correta da primeira.
as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa correta da primeira.
tanto a primeira quanto a segunda asserções são proposições falsas.
a primeira asserção é uma proposição falsa e a segunda uma proposição verdadeira.

Correlacione os algoritmos internos de ordenação de listas com sua descrição: I. Bubble sort II. Ordenação por seleção III. Ordenação por inserção IV. Shell sort V. Quick sort ( ) Escolhe-se um pivô e particiona-se a lista em duas sublistas - uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivô, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n²), no caso médio, é de O(n log n). ( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do vetor. Repetem-se essas duas operações com os n − 1 itens restantes; depois, com os n − 2 itens; até que reste apenas um elemento. ( ) Método preferido dos jogadores de cartas. A cada momento, existem duas partes na lista ¿ uma ordenada (destino) e outra não ordenada (fonte). Inicialmente, a lista destino tem apenas o primeiro elemento, e a fonte, os demais elementos. Em cada passo, a partir de i=2, seleciona-se o i-ésimo item da lista fonte. Deve-se colocá-lo no lugar apropriado na lista destino, de acordo com o critério de ordenação. ( ) É uma extensão de outro algoritmo de ordenação conhecido e permite trocas de elementos distantes um do outro, não necessariamente adjacentes. Os itens separados de h posições são rearranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é dita estar h-ordenada. ( ) Varre-se a lista, trocando de posição os elementos adjacentes fora de ordem. Varre-se a lista até que não haja mais trocas. Neste caso, a lista está ordenada. A sequência correta, de cima para baixo, é:
V, II, III, IV, I
V, IV, II, III, I
I, III, II, IV, V
I, II, III, IV, V
I, IV, V, III, II

Árvore AVL é uma árvore de busca autobalanceada. Isso significa que:
as alturas das duas subárvores a partir de cada nó diferem no máximo em duas unidades.
as alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade.
as alturas das duas subárvores a partir de cada nó são exatamente iguais.
pode possuir até duas raízes.
cada nó da árvore possui até três descendentes.