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 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:
, e . - Cada laço itera de
até , ou seja, cada um faz iterações (assumindo inteiro não-negativo). - No corpo do laço médio há uma atribuição
e um laço interno que acumula o produto em . - A pergunta é: “qual a complexidade, no pior caso?” — isto é, a complexidade de tempo assintótica quando
tende a infinito.
Passo 2
Contagem das iterações dos laços (estrutura dos laços):
- O laço externo (sobre
) executa vezes. - Para cada valor de
, o laço do meio (sobre ) executa vezes. - Para cada par
, o laço interno (sobre ) executa vezes.
Logo, o número total de execuções do corpo do laço interno é
Passo 3
Contagem das operações elementares dentro dos laços:
- A linha
é executada uma vez para cada par . Há dessas atribuições. - Dentro do laço sobre
, para cada iteração ocorre a operação de multiplicação e uma adição/atribuição . Podemos contar isso como, pelo menos, duas operações elementares por iteração de (uma multiplicação e uma adição). - Assim, as operações do laço interno somam aproximadamente
operações por iteração, totalizando aproximadamente operações desse tipo.
Passo 4
Somando todas as contribuições:
- Operações do laço interno: aproximadamente
. - Atribuições
: .
Portanto o total de operações elementares é da forma
ou, de modo assintótico, um polinômio cujo termo dominante é
.
Passo 5
Simplificação assintótica e definição da resposta:
- Para
grande, o termo de maior ordem domina, então o tempo de execução cresce como uma constante vezes . - Em notação assintótica: o tempo é
. Como também há uma constante positiva e um termo de ordem exatamente , pode-se afirmar mais fortemente que o tempo é . No pior caso, a complexidade temporal é da ordem cúbica.
Passo 6
Exemplo numérico rápido (para fixar a ideia): se
,
- o laço interno executa
vezes; - as atribuições
ocorrem vezes; - total aproximado de operações internas
.
Isso mostra como o termodomina já para 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é
, é quase sempre um algoritmo . - Não se preocupe com constantes (como o
no exemplo); em notação assintótica elas não mudam a classe de complexidade.