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).
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).
0
0
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar