Flashcard FC377470
Qual a complexidade no pior caso de um algoritmo que divide recursivamente a entrada em duas metades e intercala as metades gastando Θ(n) por nível?
Algoritmos e Lógica de Programação
Instituto Consulplan · 2023
Qual a complexidade no pior caso de um algoritmo que divide recursivamente a entrada em duas metades e intercala as metades gastando Θ(n) por nível?
Mostrar resposta e comentário
Resposta
Resposta: \(O(n\log n)\)Explicação:
Recorrência: \(T(n)=2T(n/2)+\Theta(n)\).
Pelo Teorema Mestre, \(T(n)=\Theta(n\log n)\).
Esse método é estável e requer memória adicional \(O(n)\) para o merge.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/374700
Conteúdo do catálogo FC Concursos · Atualizado em