Complexidade de Algoritmo

01/04/2019

21

Boa Tarde

Amigos,

Preciso muito da ajuda de vocês para realizar este exercicio eu não possuo muito entendimento e meus colegas da turma tambem estão com dificuldade.
Calcule a complexidade, no pior caso, do fragmento de codigo abaixo:


int i, j,k;
for (i=0; i< N; i++){
for (j=0; j< N; j++){
R[ i ] = 0;
for (k=0; k< N; k++)
R[ i ] [ j ] += A [ i ] [ k ] * B [ k ] [ j ];
}
}
Responder

Posts

06/07/2019

João Júnior

Boa Tarde

Amigos,

Preciso muito da ajuda de vocês para realizar este exercicio eu não possuo muito entendimento e meus colegas da turma tambem estão com dificuldade.
Calcule a complexidade, no pior caso, do fragmento de codigo abaixo:


int i, j,k;
for (i=0; i< N; i++){
for (j=0; j< N; j++){
R[ i ] = 0;
for (k=0; k< N; k++)
R[ i ] [ j ] += A [ i ] [ k ] * B [ k ] [ j ];
}
}


Bom, vejamos se eu me lembro. Nesse caso, o que nos interessa é saber quantas vezes o laço mais interno é executado. Bom, como não há nenhum valor de corte, ou seja que interrompa qualquer um dos laços, ou uma operação que altere o número de repetições de qualquer dos laços e, chamando o laço mais interno de f3:
Em f3, o laço acontece n vezes n e mais uma vez para finalizar o laço. Por exemplo, se n = 3, então f3 fará n[0], n[1], n[2] e quando fizer n[3] sairá do laço. Logo: f3 = n(n + 1) = n^2 + n. No entanto, quando n = 3, a operação de f3 não é realizada, logo: f3 = n(n) = n^2

Então, para mim a complexidade é O(n^2).

Por via das dúvidas veja: https://programacaodescomplicada.wordpress.com/2015/09/14/ed-aula-102-analise-de-algoritmos-notacao-grande-o/ e isso: https://www.youtube.com/user/patriciajaques1/search?query=Complexidade
Responder

Utilizamos cookies para fornecer uma melhor experiência para nossos usuários. Para saber mais sobre o uso de cookies,
consulte nossa política de privacidade. Ao continuar navegando em nosso site, você concorda com a nossa política.

Aceitar