Calcule a complexidade, no pior caso, do fragmento de código abaixo:
int i,j,k;
for(i=0; i < N; i ++){
for(j=0; j < N; j++){
R[i][j] = 0;
for(k=0; k < N; k++)
R[i][j] += A[i][k] * B[k][j];
}
}
int i,j,k;
for(i=0; i < N; i ++){
for(j=0; j < N; j++){
R[i][j] = 0;
for(k=0; k < N; k++)
R[i][j] += A[i][k] * B[k][j];
}
}
Passo 1
O enunciado pede para determinar a complexidade de tempo, no pior caso, de um trecho com três loops aninhados que inicializa R[i][j] e acumula produtos A[i][k]·B[k][j]. O conteúdo é análise de complexidade de algoritmos usando notação Big-O.
Passo 2
O primeiro loop (variável i) executa N iterações. Para cada valor de i, o segundo loop (variável j) também executa N iterações. Isso já nos dá N×N iterações para percorrer todos os pares (i,j).
Para cada par (i,j), fazemos duas operações: atribuir R[i][j]=0 (custo constante) e depois executar o terceiro loop (variável k) com N iterações, cada uma fazendo uma soma e uma multiplicação—também custo constante por iteração.
Para cada par (i,j), fazemos duas operações: atribuir R[i][j]=0 (custo constante) e depois executar o terceiro loop (variável k) com N iterações, cada uma fazendo uma soma e uma multiplicação—também custo constante por iteração.
Passo 3
Somando tudo, o número total de iterações da operação dominante (dentro do loop k) é N (do i) × N (do j) × N (do k) = N³. Termos de ordem inferior (como a inicialização R[i][j]=0) são absorvidos pela notação Big-O.
Portanto, a complexidade de tempo, no pior caso, cresce proporcionalmente a N³.
Portanto, a complexidade de tempo, no pior caso, cresce proporcionalmente a N³.
Resposta
A complexidade de tempo no pior caso é
.