5. Dada uma função de complexidade T(n) = 2T(n/2) + n, determine sua complexidade assintótica utilizando o Teorema Mestre. Resolução: Utilizando o ...
5. Dada uma função de complexidade T(n) = 2T(n/2) + n, determine sua complexidade assintótica utilizando o Teorema Mestre.
Resolução: Utilizando o Teorema Mestre, podemos ver que T(n) = aT(n/b) + f(n), onde a = 2, b = 2 e f(n) = n. Como f(n) = n = O(n^1), então a complexidade de T(n) é O(n^log_b(a)), ou seja, O(n^log_2(2)), que é O(n).
Resolução: Utilizando o Teorema Mestre, podemos ver que T(n) = aT(n/b) + f(n), onde a = 2, b = 2 e f(n) = n. Como f(n) = n = O(n^1), então a complexidade de T(n) é O(n^log_b(a)), ou seja, O(n^log_2(2)), que é O(n).
Essa pergunta também está no material:
💡 1 Resposta
Ed 
A complexidade assintótica da função T(n) = 2T(n/2) + n, utilizando o Teorema Mestre, é O(n). Isso ocorre porque a função se encaixa no caso 2 do Teorema Mestre, onde f(n) = n = O(n^1), e, portanto, a complexidade é O(n^log_2(2)), que simplifica para O(n).
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
Compartilhar