Complexidade de Algoritmo
01/04/2019
0
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 ];
}
}
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 ];
}
}
Joice Ferreira
Curtir tópico
+ 0
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 ];
}
}
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
Clique aqui para fazer login e interagir na Comunidade :)