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];
    }
}

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.

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³.

Resposta

A complexidade de tempo no pior caso é O(N^3).

Exercícios relacionados