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 dá um fragmento de código com três laços aninhados e pede a complexidade no pior caso. Informações importantes extraídas do enunciado:
  • Há três índices de laço: i, j e k.
  • Cada laço itera de 0 até N-1, ou seja, cada um faz N iterações (assumindo N inteiro não-negativo).
  • No corpo do laço médio há uma atribuição R[i][j]=0 e um laço interno que acumula o produto A[i][k]*B[k][j] em R[i][j].
  • A pergunta é: “qual a complexidade, no pior caso?” — isto é, a complexidade de tempo assintótica quando N tende a infinito.

Passo 2

Contagem das iterações dos laços (estrutura dos laços):
  • O laço externo (sobre i) executa N vezes.
  • Para cada valor de i, o laço do meio (sobre j) executa N vezes.
  • Para cada par (i,j), o laço interno (sobre k) executa N vezes.
Logo, o número total de execuções do corpo do laço interno é
N \times N \times N = N^{3}.

Passo 3

Contagem das operações elementares dentro dos laços:
  • A linha R[i][j]=0 é executada uma vez para cada par (i,j). Há N\times N=N^{2} dessas atribuições.
  • Dentro do laço sobre k, para cada iteração ocorre a operação de multiplicação A[i][k] * B[k][j] e uma adição/atribuição R[i][j] += \dots. Podemos contar isso como, pelo menos, duas operações elementares por iteração de k (uma multiplicação e uma adição).
  • Assim, as operações do laço interno somam aproximadamente 2 operações por iteração, totalizando aproximadamente 2N^{3} operações desse tipo.

Passo 4

Somando todas as contribuições:
  • Operações do laço interno: aproximadamente 2N^{3}.
  • Atribuições R[i][j]=0: N^{2}.
    Portanto o total de operações elementares é da forma
2N^{3} + N^{2},
ou, de modo assintótico, um polinômio cujo termo dominante é N^{3}.

Passo 5

Simplificação assintótica e definição da resposta:
  • Para N grande, o termo de maior ordem domina, então o tempo de execução cresce como uma constante vezes N^{3}.
  • Em notação assintótica: o tempo é O\left(N^{3}\right). Como também há uma constante positiva e um termo de ordem exatamente N^{3}, pode-se afirmar mais fortemente que o tempo é \Theta\left(N^{3}\right). No pior caso, a complexidade temporal é da ordem cúbica.

Passo 6

Exemplo numérico rápido (para fixar a ideia): se N=10,
  • o laço interno executa 10^{3}=1000 vezes;
  • as atribuições R[i][j]=0 ocorrem 10^{2}=100 vezes;
  • total aproximado de operações internas 2\cdot1000+100=2100.
    Isso mostra como o termo N^{3} domina já para N moderadamente pequeno.

Passo 7

Dica prática para prova (como reconhecer rápido):
  • Sempre conte quantas vezes cada laço é executado multiplicando os números de iterações em laços aninhados.
  • Se há três laços aninhados que vão até N, é quase sempre um algoritmo \Theta\left(N^{3}\right).
  • Não se preocupe com constantes (como o 2 no exemplo); em notação assintótica elas não mudam a classe de complexidade.

Resposta

O\left(N^{3}\right) (mais precisamente \Theta\left(N^{3}\right))

Exercícios relacionados